#include<queue>
#include<fstream>
#define inf 0x3f3f3f3f
using namespace std;
long d[50000];
class cmp
{public: bool operator() (int& x,int& y) 
{return (d[x]<d[y]);}};
struct muchie{int y,c;};
int main()
{priority_queue< int, vector<int>, cmp > p;
vector< vector <muchie> > a(50000);
ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
muchie mm;
int n,m,x,i,xx;
f>>n>>m;
for(i=1;i<=m;i++)
	{f>>x>>mm.y>>mm.c;
a[x].push_back(mm);}

for(i=2;i<=n;i++)
	d[i]=inf;
p.push(1);
while(!p.empty())
{xx=p.top();
p.pop();

	for(i=0;i<a[xx].size();i++)
		if(d[a[xx][i].y]>=d[xx]+a[xx][i].c)
	{d[a[xx][i].y]=d[xx]+a[xx][i].c;
	p.push(a[xx][i].y);
	}	
}
for(i=2;i<=n;i++)
if(d[i]==inf)
h<<"0 ";
else h<<d[i]<<' ';	
return 0;}