#include<iostream>
#include<fstream>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
struct muchie{int y,c;};
long d[50000];
int main()
{ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
int n,m,x,i,xx,min;
bool viz[50000];

vector< vector <muchie> > v(50000);
queue<int> q;
muchie mm;
f>>n>>m;
for(i=1;i<=m;i++)
	{f>>x>>mm.y>>mm.c;
v[x].push_back(mm);}

for(i=2;i<=n;i++)
	d[i]=inf;
	d[1]=0;
q.push(1);
viz[1]=1;
	while(!q.empty())
	{xx=q.front();
	q.pop();
viz[xx]=0;
for(i=0;i<v[xx].size();i++)
	if(d[v[xx][i].y]>d[xx]+v[xx][i].c)
		{d[v[xx][i].y]=d[xx]+v[xx][i].c;
		if(viz[v[xx][i].y]==0)
	{q.push(v[xx][i].y);
	viz[v[xx][i].y]=1;}}}
	
	for(i=2;i<=n;i++)
if(d[i]==inf)
h<<"0 ";
else	
h<<d[i]<<" ";
	
	
	
	
	return 0;}