qwq

#include<bits/stdc++.h>
using namespace std;
struct st{
	int v,w;
};
vector <st> t[100005];
int l[100005];
int c[100005];
st d[100005];
bool a[100005];
int qwq;
void put (int i,int j){
	qwq++;
	d[qwq].v=i;
	d[qwq].w=j;
	int v1=qwq;
	while (d[v1].v<d[v1/2].v){
		swap(d[v1],d[v1/2]);
		v1=v1/2;
	}
	return ;
}
int get(){
	int i=1;
	int x114514=d[1].v;
	d[1].v=d[qwq].v;
	while (i*2<qwq){
		if (d[i].v>d[i*2].v&&(d[i*2].v<d[i*2+1].v||i*2+1==qwq)){
			swap(d[i],d[i*2]);
			i=i*2;
		}else if(d[i].v>d[i*2+1].v&&i*2+1<qwq){
			swap(d[i],d[i*2+1]);
			i=i*2+1;
		}else{
			break;
		}
	}
	qwq--;
	return x114514;
}
int main(){
	int n,m,ewe;
	cin>>n>>m>>ewe;
	for (int i=1;i<=n;i++){
		c[i]=2147483647;
	}
	for (int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		t[x].push_back(st{y,z});
		l[x]++;
	}
	c[1]=0; 
	a[1]=true;
	int x=1;
	for (int i=1;i<=n;i++){
		for (int j=0;j<l[x];j++){
			if (!a[t[x][j].v]){
				if (c[x]+t[x][j].w<c[t[x][j].v]){
					c[t[x][j].v]=c[x]+t[x][j].w;
					put(c[t[x][j].v],t[x][j].v);
					cout<<qwq<<endl;
				}
			}
		}
		int awa=get();
		while (a[awa]){
			awa=get();
		}
		x=awa;
		a[awa]=true;
	}
	for (int i=1;i<=n;i++){
		cout<<c[i]<<' ';
	}
	return 0;
}