#include <iostream>
#include <unordered_map>
#include <queue>
#include <climits>
using namespace std;
 
int main() {
 
	long long n,m;
	cin>>n>>m;
 
	unordered_map<long long,unordered_map<long long,long long> > Map;
	for(long long i=0;i<m;i++)
	{
		long long a,b,c;
		cin>>a>>b>>c;
		if(Map.count(a-1) > 0 && Map[a-1].count(b-1) > 0)
		{
			Map[a-1][b-1]=min(c,Map[a-1][b-1]);
		}
		else
		{
			Map[a-1][b-1]=c;
		}
	}
 
	priority_queue<long long> PQ;
	PQ.push(0);
 
	long long DP[n];
	for(long long i=0;i<n;i++)
	{
		DP[i] = LLONG_MAX;
	}
	DP[0]=0;
 
	while(!PQ.empty())
	{
		long long x = PQ.top();
		PQ.pop();
 
		for(auto it=Map[x].begin();it!=Map[x].end();it++)
		{
			if(DP[it->first] > DP[x] + it->second)
			{
				DP[it->first] = DP[x] + it->second;
				PQ.push(it->first);
			}
		}
	}
 
	for(long long i=0;i<n;i++)
	{
		cout<<DP[i]<<" ";
	}
	cout<<endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8Y2xpbWl0cz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewoJCglsb25nIGxvbmcgbixtOwoJY2luPj5uPj5tOwoJCgl1bm9yZGVyZWRfbWFwPGxvbmcgbG9uZyx1bm9yZGVyZWRfbWFwPGxvbmcgbG9uZyxsb25nIGxvbmc+ID4gTWFwOwoJZm9yKGxvbmcgbG9uZyBpPTA7aTxtO2krKykKCXsKCQlsb25nIGxvbmcgYSxiLGM7CgkJY2luPj5hPj5iPj5jOwoJCWlmKE1hcC5jb3VudChhLTEpID4gMCAmJiBNYXBbYS0xXS5jb3VudChiLTEpID4gMCkKCQl7CgkJCU1hcFthLTFdW2ItMV09bWluKGMsTWFwW2EtMV1bYi0xXSk7CgkJfQoJCWVsc2UKCQl7CgkJCU1hcFthLTFdW2ItMV09YzsKCQl9Cgl9CgkKCXByaW9yaXR5X3F1ZXVlPGxvbmcgbG9uZz4gUFE7CglQUS5wdXNoKDApOwoJCglsb25nIGxvbmcgRFBbbl07Cglmb3IobG9uZyBsb25nIGk9MDtpPG47aSsrKQoJewoJCURQW2ldID0gTExPTkdfTUFYOwoJfQoJRFBbMF09MDsKCQoJd2hpbGUoIVBRLmVtcHR5KCkpCgl7CgkJbG9uZyBsb25nIHggPSBQUS50b3AoKTsKCQlQUS5wb3AoKTsKCQkKCQlmb3IoYXV0byBpdD1NYXBbeF0uYmVnaW4oKTtpdCE9TWFwW3hdLmVuZCgpO2l0KyspCgkJewoJCQlpZihEUFtpdC0+Zmlyc3RdID4gRFBbeF0gKyBpdC0+c2Vjb25kKQoJCQl7CgkJCQlEUFtpdC0+Zmlyc3RdID0gRFBbeF0gKyBpdC0+c2Vjb25kOwoJCQkJUFEucHVzaChpdC0+Zmlyc3QpOwoJCQl9CgkJfQoJfQoJCglmb3IobG9uZyBsb25nIGk9MDtpPG47aSsrKQoJewoJCWNvdXQ8PERQW2ldPDwiICI7Cgl9Cgljb3V0PDxlbmRsOwoJcmV0dXJuIDA7Cn0=

MTAgMjAKOCA1IDEKOSAxMCAyCjcgOSA4CjkgOCA4CjEwIDkgOQo3IDggMTAKOCA5IDIKNyAxMCAxMAo0IDUgOAo1IDYgMQo0IDIgMQo1IDMgNgoxMCA3IDMKMyA1IDIKNSA0IDcKMSAyIDkKMiAzIDIKNiA3IDUKMyA0IDEwCjMgMiAxMA==

10 20
8 5 1
9 10 2
7 9 8
9 8 8
10 9 9
7 8 10
8 9 2
7 10 10
4 5 8
5 6 1
4 2 1
5 3 6
10 7 3
3 5 2
5 4 7
1 2 9
2 3 2
6 7 5
3 4 10
3 2 10