#include<fstream>
#include<vector>
#include<queue>
using namespace std;
const int pinf=0x3f3f3f3f; 
struct muchie {int y,c;};
int main()
{ifstream f("dijkstra.in"); 
ofstream h("dijkstra.out");
vector< vector <muchie> > v(50000);
queue<int> p;
int n,m,i,x,y,d[50000],xx;
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]=pinf;
d[1]=0;
	p.push(1);
while(!p.empty())
	{xx=p.front();
		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]==0)
{d[v[xx][i].y]=d[xx]+v[xx][i].c;
		p.push(v[xx][i].y);	}
	p.pop();
	}
	
	for(i=2;i<=n;i++)
		h<<d[i]<<' ';
return 0;}