n,m,T=map(int,input().split())
graph_a=[[] for _ in range(n+1)]
graph_b=[[] for _ in range(n+1)]
double_graph_a=[[0]*(n+1) for _ in range(n+1)]
double_graph_b=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
u,v,t=map(int,input().split())
graph_a[v].append(u)
graph_b[v].append(t)
if u==1:
double_graph_a[v][2]=t
double_graph_b[v][2]=1
next_n=n+1
for c in range(3,next_n):
for v in range(2,next_n):
for i,nx in enumerate(graph_a[v]):
if double_graph_a[nx][c-1]:
dist=double_graph_a[nx][c-1]+graph_b[v][i]
if dist<=T and (not double_graph_a[v][c] or double_graph_a[v][c]>dist):
double_graph_a[v][c]=dist
double_graph_b[v][c]=nx
for i in range(n,0,-1):
if double_graph_b[n][i]:
break
res=[n]
while double_graph_b[res[-1]][i]!=1:
res.append(double_graph_b[res[-1]][i])
i-=1
res+=[1]
print(len(res))
print(" ".join(map(str,res[::-1])))
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
// #define int long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a,b,sizeof(a))
#define goog(tno) cout << "Case #" << tno <<": "
#define vi vector<int>
#define vii vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define in(a) for(auto &x: a)cin>>x;
#define out(a) for(auto x: a){cout<<x<<' ';}cout<<'\n';
#define inf 1e9+10
//#define mm 1000000007 998244353
void print(bool n){if(n)cout<<"YES";else cout<<"NO";cout<<'\n';}
vector<pii> adj[5000];
int p[5000][5000];
int n;
int dp[5000][5000];
int fun(int i,int j){
if(i==n-1)return (j==0)?0:inf;
if(j==0)return inf;
if(dp[i][j]!=-1)return dp[i][j];
int ans=inf;
for(auto u: adj[i]){
int x=u.se+fun(u.fi,j-1);
if(x<ans){
ans=x;
p[i][j]=u.fi;
}
}
return dp[i][j] = ans;
}
signed main(){
fastio
int m,t;
cin>>n>>m>>t;
fill(dp,-1);
rep(i,0,m){
int u,v,x;
cin>>u>>v>>x;
--u,--v;
adj[u].emplace_back(v,x);
}
int l;
rep(i,0,n){
if(fun(0,i)<=t)l=i;
}
cout<<l+1<<'\n';
int x=0;
while(l){
cout<<x+1<<' ';
x=p[x][l];
l--;
}
cout<<x+1;
return 0;
}287A - IQ Test | 1108A - Two distinct points |
1064A - Make a triangle | 1245C - Constanze's Machine |
1005A - Tanya and Stairways | 1663F - In Every Generation |
1108B - Divisors of Two Integers | 1175A - From Hero to Zero |
1141A - Game 23 | 1401B - Ternary Sequence |
598A - Tricky Sum | 519A - A and B and Chess |
725B - Food on the Plane | 154B - Colliders |
127B - Canvas Frames | 107B - Basketball Team |
245A - System Administrator | 698A - Vacations |
1216B - Shooting | 368B - Sereja and Suffixes |
1665C - Tree Infection | 1665D - GCD Guess |
29A - Spit Problem | 1097B - Petr and a Combination Lock |
92A - Chips | 1665B - Array Cloning Technique |
1665A - GCD vs LCM | 118D - Caesar's Legions |
1598A - Computer Game | 1605A - AM Deviation |