#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
ifstream fin("dijkstra.in"); ofstream fout("dijkstra.out");

int n, m;
multiset<pair<int, int> > q;
vector<vector<pair<int, int>> > g;
bool v[50010];
int d[50010];





void dijkstra(){
int s=1;
d[1]=0;
q.insert(mp(0, s) );

    while(!q.empty()){
        int f=q.begin()->sc;
        q.erase(q.begin());
        v[f]=true;

        for(int i=0 ;i<g[f].size(); i++){

            if(!v[g[f][i].ft ] ){
                if(d[f]+g[f][i].sc<d[g[f][i].ft ]){

                    if(d[g[f][i].ft]<=1000*1000*1000 ){q.erase(q.find(mp(d[g[f][i].ft ], g[f][i].ft) ) );}

                    d[g[f][i].ft ]=d[f]+g[f][i].sc;
                    q.insert(mp(d[g[f][i].ft ], g[f][i].ft) );
                }
            }


        }

    }


}





int main(){
fin>>n>>m;
for(int i=1; i<=n; i++){d[i]=1000*1000*1000+1;}
g.resize(n+10);
for(int i=0; i<m;i++){
    int x, y, l;
    fin>>x>>y>>l;
    g[x].pb(mp(y, l) );
}

dijkstra();


for(int i=2; i<=n; i++){
        if(d[i]>1000*1000*1000){fout<<0<<" "; continue;}
    fout<<d[i]<<" ";
}



return 0;
}