#include<bits/stdc++.h>
using namespace std;
#define ll long
#define iPair pair<ll,ll>
int main()
{ ll n,m,i,x,y,u,v,z,w;
	cin>>n>>m;
	vector<vector<iPair > >vec(m+1);
	ll dst[n+9];
	for(i=0;i<m;i++)
	{
		cin>>x>>y>>z;
		vec[x].push_back(make_pair(y,z));
		vec[y].push_back(make_pair(x,z));
	}
	for(i=1;i<=n;i++)
	{
		dst[i]=999;
	}
	dst[1]=0;
	priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
	pq.push(make_pair(1,0));
	while(!pq.empty())
	{
		u=pq.top().first;
		pq.pop();
		for(i=0;i<vec[u].size();i++)
		{
			v=vec[u][i].first;
			w=vec[u][i].second;
			if(dst[v]>dst[u]+w){
			dst[v]=dst[u]+w;
			pq.push(make_pair(v,dst[v]));}
		}
 
 
	}
	for(i=1;i<=n;i++)
	{
		cout<<dst[i]<<" ";
	}
 
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nCiNkZWZpbmUgaVBhaXIgcGFpcjxsbCxsbD4KaW50IG1haW4oKQp7IGxsIG4sbSxpLHgseSx1LHYseix3OwoJY2luPj5uPj5tOwoJdmVjdG9yPHZlY3RvcjxpUGFpciA+ID52ZWMobSsxKTsKCWxsIGRzdFtuKzldOwoJZm9yKGk9MDtpPG07aSsrKQoJewoJCWNpbj4+eD4+eT4+ejsKCQl2ZWNbeF0ucHVzaF9iYWNrKG1ha2VfcGFpcih5LHopKTsKCQl2ZWNbeV0ucHVzaF9iYWNrKG1ha2VfcGFpcih4LHopKTsKCX0KCWZvcihpPTE7aTw9bjtpKyspCgl7CgkJZHN0W2ldPTk5OTsKCX0KCWRzdFsxXT0wOwoJcHJpb3JpdHlfcXVldWU8IGlQYWlyLCB2ZWN0b3IgPGlQYWlyPiAsIGdyZWF0ZXI8aVBhaXI+ID4gcHE7CglwcS5wdXNoKG1ha2VfcGFpcigxLDApKTsKCXdoaWxlKCFwcS5lbXB0eSgpKQoJewoJCXU9cHEudG9wKCkuZmlyc3Q7CgkJcHEucG9wKCk7CgkJZm9yKGk9MDtpPHZlY1t1XS5zaXplKCk7aSsrKQoJCXsKCQkJdj12ZWNbdV1baV0uZmlyc3Q7CgkJCXc9dmVjW3VdW2ldLnNlY29uZDsKCQkJaWYoZHN0W3ZdPmRzdFt1XSt3KXsKCQkJZHN0W3ZdPWRzdFt1XSt3OwoJCQlwcS5wdXNoKG1ha2VfcGFpcih2LGRzdFt2XSkpO30KCQl9CgkJCgkJCgl9Cglmb3IoaT0xO2k8PW47aSsrKQoJewoJCWNvdXQ8PGRzdFtpXTw8IiAiOwoJfQoKfQ==

MyAyCjEgMiAzCjEgMyA3OA==

3 2
1 2 3
1 3 78