#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,z;
	node(int x,int z):x(x),z(z){} 
};
priority_queue<pair<int,int> > q;
vector < node > g[10100];
int n,m,k,a,b,c,f[10100][110],vis[10100][110];
int main(){
	cin>>n>>m>>k;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		g[a].push_back(node(b,c)); 
	}
    f[1][0]=0; 
//    vis[1][0]=1;
    q.push(make_pair(0,1)); 
    while(!q.empty()){
    	int h=q.top().second,u=abs(q.top().first);
    	q.pop();
    	
    	if(vis[h][u%k]==1) continue;
    	vis[h][u%k]=1;
    	int j=u%k;
    	cout<<g[h].size();
    	for(int i=0;i<g[h].size();i++){
    		cout<<i<<endl;
    		int v=g[u][i].x,w=g[u][i].z;//<-- 
    		cout<<i<<endl;
//    		int j=u%k;
    	    if(u>=w){
//    	    	if(vis[v][(j+1)%k]==1) continue;
    	    	if(f[h][j]+1<f[v][(j+1)%k]){
    	    		f[v][(j+1)%k]=f[h][j]+1;
//    	    		vis[v][(u+1)%k]=1; 
                    cout<<":::";
    	    		q.push(make_pair(-f[v][(j+1)%k],v));
				}
			}
			else{
				int d=ceil((w-f[h][j])*1.0/k);
//				if(vis[v][(j+1)%k]==1) continue;
				if(f[h][j]+d*k+1<f[v][(j+1)%k]){
					f[v][(j+1)%k]=f[h][j]+d*k+1;
					cout<<";;;";
//					vis[v][(u+1)%k]=1;
					q.push(make_pair(-f[v][(j+1)%k],v));
				}
			}
		}cout<<h<<' '<<u<<'\n';cout<<q.size()<<endl;
	}
	if(f[n][0]==0x3f3f3f3f) cout<<-1;
	else cout<<f[n][0];
}