#include<bits/stdc++.h>
#include<vector>
using namespace std;
long long d[20000][3],e[10000][100],ex[1000000][2],e1=0,e2=1;
struct two{
	long long k,l;
};
vector<two> f[10000];
int main(){
	long long a,b,c,o=0,p=0;
	cin>>a>>b>>c;
	for(long long x=0;x<b;x++){
		cin>>d[x][0]>>d[x][1]>>d[x][2];
		d[x][0]--;
		d[x][1]--;
		two y;
		y.k=d[x][1],y.l=d[x][2];
		f[d[x][0]].push_back(y);
	}
	for(long long x=0;x<a;x++){
		for(long long y=0;y<c;y++){
			e[x][y]=1000000000;
		}
	}
	e[0][0]=0,ex[0][0]=ex[0][1]=0;
	while(e1<e2 && e[a-1][0]==1000000000){
		long long j=ex[e1][0],z=ex[e1][1]%c;
		for(long long y=0;y<f[j].size();y++){
				p=e[f[j][y].k][(z+1)%c];
				if(f[j][y].l>e[j][z]){
					e[f[j][y].k][(z+1)%c]=min(e[f[j][y].k][(z+1)%c],(long long)ceil((f[j][y].l-e[j][z])*1.0/c)*c+e[j][z]+1);
					o=(long long)ceil((f[j][y].l-e[j][z])*1.0/c)*c+e[j][z]+1;
				}else if(e[j][z]<1000000000){
					e[f[j][y].k][(z+1)%c]=min(e[f[j][y].k][(z+1)%c],e[j][z]+1);
					o=e[j][z]+1;
				}
				if(o<p){
					ex[e2][0]=f[j][y].k,ex[e2][1]=o,e2++;
				}
		}
		e1++;
	}
	for(long long x=0;x<a;x++){
		for(long long y=0;y<c;y++){
			if(e[x][y]==1000000000){
				cout<<"?";
			}else{
				cout<<e[x][y];
			}
		}
		cout<<endl;
	}
	if(e[a-1][0]==1000000000){
		cout<<-1;
	}else{
		cout<<e[a-1][0];
	}
}

错了#8~10，#19，#22