#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ff first
#define ss second
#define fo(i,n) for(int i=0;i<n;i++)
#define fod(i,n) for(int i=n-1;i>=0;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define all(x) x.begin(),x.end()
#define SET(x,v) memset(x,v,sizeof(x))
#define si set<int>
#define pb(i) push_back(i)
#define sll set<long long>
#define vs vector<string>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define vpii vector<pair<int,int>>
#define ll long long int
#define vi vector<ll>
#define mod 1000000007
#define tc(t) int t; cin>>t; while(t--)
#define sfm(a,m,n) ll a[m][n]; fo(i,m) fo(j,n) cin>>a[i][j]
#define sfarr(a,n) ll a[n]; fo(i,n) cin>>a[i]
#define sfv(v,n) vi v(n); for(ll &i:v) cin>>i
// int f[1000001];
// int prime[1000001];
// void sieve(){
// prime[0]=prime[1]=0;
// For(i,2,1000000) prime[i]=1;
// for(int i=2;i*i<=1000000;i++){
// if(prime[i]){
// for(ll j=i*i;j<=1000000;j+=i)
// prime[j]=0;
// }
// }
// }
// int power(int a,int b){
// int r=1;
// while(b){
// if(b&1){
// r=(r*1ll*a)%mod;
// b--;
// }
// else{
// a=(a*1ll*a)%mod;
// b>>=1;
// }
// }
// return r;
// }
// void factorial(){
// f[0]=f[1]=1;
// For(i,2,1000000) f[i]=(f[i-1]*1ll*i)%mod;
// }
// int nCr(int a,int b){
// if(b>a) return 0;
// factorial();
// int r=f[a];
// r=(r*1ll*power(f[b],mod-2))%mod;
// r=(r*1ll*power(f[a-b],mod-2))%mod;
// return r;
// }
// vi z_algo(string s){
// ll n=s.length(),l=0,r=0;
// vi z(n);
// For(i,1,n-1){
// if(i<=r) z[i]=min(r-i+1,z[i-l]);
// while(z[i]+i<n && s[z[i]]==s[i+z[i]]) z[i]++;
// if(i+z[i]-1>r) l=i,r=i+z[i]-1;
// }
// return z;
// }
// int parent[1000001];
// int ranker[1000001];
// int findpar(int node){
// if(node==parent[node])
// return node;
// return parent[node]=findpar(parent[node]);
// }
// void connect(int u,int v){
// u=findpar(u);
// v=findpar(v);
// if(u==v) return;
// if(ranker[u]<ranker[v])
// parent[u]=v;
// else if(ranker[u]>ranker[v])
// parent[v]=u;
// else{
// parent[v]=u;
// ranker[u]++;
// }
// }
vector<bool> vis(1000001,0);
vector<int> g[1000001];
// void graph(vector<int> g[],int e,bool t){
// fo(i,e){
// int u,v; cin>>u>>v;
// g[u].pb(v);
// if(!t)
// g[v].pb(u);
// }
// }
// void dfs(int node){
// vis[node]=1;
// for(int child:g[node]){
// if(!vis[child])
// dfs(child);
// }
// }
// priority_queue <int, vector<int>, greater<int>> g;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m; cin>>n>>m;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> hp;
vi dist(n+1,1e18);
vector<pair<ll,ll>> g[1000001];
fo(i,m){
ll a,b,c; cin>>a>>b>>c;
g[a].pb(make_pair(c,b));
}
hp.push({0,1});
dist[1]=0;
while(hp.size()){
pair<int,int> pq=hp.top();
int wt=hp.top().ff,node=hp.top().ss;
hp.pop();
if(vis[pq.ss]) continue;
else vis[pq.ss]=1;
for(auto child:g[node]){
if(dist[node]+wt<dist[child.ss]){
dist[child.ss]=dist[node]+wt;
hp.push({child.ff,child.ss});
}
}
}
For(i,1,n) cout<<dist[i]<<" ";
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vICNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KLy8gI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+Ci8vIHVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwovLyAjZGVmaW5lIG9yZGVyZWRfc2V0IHRyZWU8aW50LCBudWxsX3R5cGUsIGxlc3M8aW50PiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT4KCiNkZWZpbmUgZmYgICAgICAgICAgICAgIGZpcnN0CiNkZWZpbmUgc3MgICAgICAgICAgICAgIHNlY29uZAojZGVmaW5lIGZvKGksbikgICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQojZGVmaW5lIGZvZChpLG4pICAgICAgICBmb3IoaW50IGk9bi0xO2k+PTA7aS0tKQojZGVmaW5lIEZvcihpLGEsYikgICAgICBmb3IoaW50IGk9YTtpPD1iO2krKykKI2RlZmluZSBhbGwoeCkgICAgICAgICAgeC5iZWdpbigpLHguZW5kKCkKI2RlZmluZSBTRVQoeCx2KSAgICAgICAgbWVtc2V0KHgsdixzaXplb2YoeCkpCiNkZWZpbmUgc2kgICAgICAgICAgICAgIHNldDxpbnQ+CiNkZWZpbmUgcGIoaSkgICAgICAgICAgIHB1c2hfYmFjayhpKQojZGVmaW5lIHNsbCAgICAgICAgICAgICBzZXQ8bG9uZyBsb25nPgojZGVmaW5lIHZzICAgICAgICAgICAgICB2ZWN0b3I8c3RyaW5nPgojZGVmaW5lIHllcyAgICAgICAgICAgICBjb3V0PDwiWUVTXG4iCiNkZWZpbmUgbm8gICAgICAgICAgICAgIGNvdXQ8PCJOT1xuIgojZGVmaW5lIHZwaWkgICAgICAgICAgICB2ZWN0b3I8cGFpcjxpbnQsaW50Pj4KI2RlZmluZSBsbCAgICAgICAgICAgICAgbG9uZyBsb25nIGludAojZGVmaW5lIHZpICAgICAgICAgICAgICB2ZWN0b3I8bGw+CiNkZWZpbmUgbW9kICAgICAgICAgICAgIDEwMDAwMDAwMDcKI2RlZmluZSB0Yyh0KSAgICAgICAgICAgaW50IHQ7IGNpbj4+dDsgd2hpbGUodC0tKQojZGVmaW5lIHNmbShhLG0sbikgICAgICBsbCBhW21dW25dOyBmbyhpLG0pIGZvKGosbikgY2luPj5hW2ldW2pdCiNkZWZpbmUgc2ZhcnIoYSxuKSAgICAgIGxsIGFbbl07IGZvKGksbikgY2luPj5hW2ldCiNkZWZpbmUgc2Z2KHYsbikgICAgICAgIHZpIHYobik7IGZvcihsbCAmaTp2KSBjaW4+PmkKLy8gaW50IGZbMTAwMDAwMV07Ci8vIGludCBwcmltZVsxMDAwMDAxXTsKLy8gdm9pZCBzaWV2ZSgpewovLyAgICAgcHJpbWVbMF09cHJpbWVbMV09MDsKLy8gICAgIEZvcihpLDIsMTAwMDAwMCkgcHJpbWVbaV09MTsKLy8gICAgIGZvcihpbnQgaT0yO2kqaTw9MTAwMDAwMDtpKyspewovLyAgICAgICAgIGlmKHByaW1lW2ldKXsKLy8gICAgICAgICAgICAgZm9yKGxsIGo9aSppO2o8PTEwMDAwMDA7ais9aSkKLy8gICAgICAgICAgICAgcHJpbWVbal09MDsKLy8gICAgICAgICB9Ci8vICAgICB9Ci8vIH0KLy8gaW50IHBvd2VyKGludCBhLGludCBiKXsKLy8gICAgIGludCByPTE7Ci8vICAgICB3aGlsZShiKXsKLy8gICAgICAgICBpZihiJjEpewovLyAgICAgICAgICAgICByPShyKjFsbCphKSVtb2Q7Ci8vICAgICAgICAgICAgIGItLTsKLy8gICAgICAgICB9Ci8vICAgICAgICAgZWxzZXsKLy8gICAgICAgICAgICAgYT0oYSoxbGwqYSklbW9kOwovLyAgICAgICAgICAgICBiPj49MTsKLy8gICAgICAgICB9Ci8vICAgICB9Ci8vICAgICByZXR1cm4gcjsKLy8gfQovLyB2b2lkIGZhY3RvcmlhbCgpewovLyAgICAgZlswXT1mWzFdPTE7Ci8vICAgICBGb3IoaSwyLDEwMDAwMDApIGZbaV09KGZbaS0xXSoxbGwqaSklbW9kOwovLyB9Ci8vIGludCBuQ3IoaW50IGEsaW50IGIpewovLyAgICAgaWYoYj5hKSByZXR1cm4gMDsKLy8gICAgICBmYWN0b3JpYWwoKTsKLy8gICAgICBpbnQgcj1mW2FdOyAKLy8gICAgICByPShyKjFsbCpwb3dlcihmW2JdLG1vZC0yKSklbW9kOwovLyAgICAgIHI9KHIqMWxsKnBvd2VyKGZbYS1iXSxtb2QtMikpJW1vZDsKLy8gICAgICByZXR1cm4gcjsKLy8gfQovLyB2aSB6X2FsZ28oc3RyaW5nIHMpewovLyAgICAgbGwgbj1zLmxlbmd0aCgpLGw9MCxyPTA7Ci8vICAgICB2aSB6KG4pOwovLyAgICAgRm9yKGksMSxuLTEpewovLyAgICAgICAgIGlmKGk8PXIpIHpbaV09bWluKHItaSsxLHpbaS1sXSk7Ci8vICAgICAgICAgd2hpbGUoeltpXStpPG4gJiYgc1t6W2ldXT09c1tpK3pbaV1dKSB6W2ldKys7Ci8vICAgICAgICAgaWYoaSt6W2ldLTE+cikgbD1pLHI9aSt6W2ldLTE7Ci8vICAgICB9Ci8vICAgICByZXR1cm4gejsKLy8gfQovLyBpbnQgcGFyZW50WzEwMDAwMDFdOwovLyBpbnQgcmFua2VyWzEwMDAwMDFdOwovLyBpbnQgZmluZHBhcihpbnQgbm9kZSl7Ci8vICAgICBpZihub2RlPT1wYXJlbnRbbm9kZV0pCi8vICAgICByZXR1cm4gbm9kZTsKLy8gICAgIHJldHVybiBwYXJlbnRbbm9kZV09ZmluZHBhcihwYXJlbnRbbm9kZV0pOwovLyB9Ci8vIHZvaWQgY29ubmVjdChpbnQgdSxpbnQgdil7Ci8vICAgICB1PWZpbmRwYXIodSk7Ci8vICAgICB2PWZpbmRwYXIodik7Ci8vICAgICBpZih1PT12KSByZXR1cm47Ci8vICAgICBpZihyYW5rZXJbdV08cmFua2VyW3ZdKQovLyAgICAgcGFyZW50W3VdPXY7Ci8vICAgICBlbHNlIGlmKHJhbmtlclt1XT5yYW5rZXJbdl0pCi8vICAgICBwYXJlbnRbdl09dTsKLy8gICAgIGVsc2V7Ci8vICAgICAgICAgcGFyZW50W3ZdPXU7Ci8vICAgICAgICAgcmFua2VyW3VdKys7Ci8vICAgICB9Ci8vIH0KdmVjdG9yPGJvb2w+IHZpcygxMDAwMDAxLDApOwp2ZWN0b3I8aW50PiBnWzEwMDAwMDFdOwovLyB2b2lkIGdyYXBoKHZlY3RvcjxpbnQ+IGdbXSxpbnQgZSxib29sIHQpewovLyAgICAgZm8oaSxlKXsKLy8gICAgICAgICBpbnQgdSx2OyBjaW4+PnU+PnY7Ci8vICAgICAgICAgZ1t1XS5wYih2KTsKLy8gICAgICAgICBpZighdCkKLy8gICAgICAgICBnW3ZdLnBiKHUpOwovLyAgICAgfQovLyB9Ci8vIHZvaWQgZGZzKGludCBub2RlKXsKLy8gICAgIHZpc1tub2RlXT0xOwovLyAgICAgZm9yKGludCBjaGlsZDpnW25vZGVdKXsKLy8gICAgICAgICBpZighdmlzW2NoaWxkXSkKLy8gICAgICAgICBkZnMoY2hpbGQpOwovLyAgICAgfQovLyB9Ci8vIHByaW9yaXR5X3F1ZXVlIDxpbnQsIHZlY3RvcjxpbnQ+LCBncmVhdGVyPGludD4+IGc7CnNpZ25lZCBtYWluKCl7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBpbnQgbixtOyBjaW4+Pm4+Pm07CiAgICBwcmlvcml0eV9xdWV1ZTxwYWlyPGludCxpbnQ+LHZlY3RvcjxwYWlyPGludCxpbnQ+PixncmVhdGVyPHBhaXI8aW50LGludD4+PiBocDsKICAgIHZpIGRpc3QobisxLDFlMTgpOwogICAgdmVjdG9yPHBhaXI8bGwsbGw+PiBnWzEwMDAwMDFdOwogICAgZm8oaSxtKXsKICAgICAgICBsbCBhLGIsYzsgY2luPj5hPj5iPj5jOwogICAgICAgIGdbYV0ucGIobWFrZV9wYWlyKGMsYikpOwogICAgfQogICAgaHAucHVzaCh7MCwxfSk7CiAgICBkaXN0WzFdPTA7CiAgICB3aGlsZShocC5zaXplKCkpewogICAgICAgIHBhaXI8aW50LGludD4gcHE9aHAudG9wKCk7CiAgICAgICAgaW50IHd0PWhwLnRvcCgpLmZmLG5vZGU9aHAudG9wKCkuc3M7CiAgICAgICAgaHAucG9wKCk7CiAgICAgICAgaWYodmlzW3BxLnNzXSkgY29udGludWU7CiAgICAgICAgZWxzZSB2aXNbcHEuc3NdPTE7CiAgICAgICAgZm9yKGF1dG8gY2hpbGQ6Z1tub2RlXSl7CiAgICAgICAgICAgIGlmKGRpc3Rbbm9kZV0rd3Q8ZGlzdFtjaGlsZC5zc10pewogICAgICAgICAgICAgICAgZGlzdFtjaGlsZC5zc109ZGlzdFtub2RlXSt3dDsKICAgICAgICAgICAgICAgIGhwLnB1c2goe2NoaWxkLmZmLGNoaWxkLnNzfSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBGb3IoaSwxLG4pIGNvdXQ8PGRpc3RbaV08PCIgIjsKcmV0dXJuIDA7Cn0KCg==