#include<fstream>
#include<queue>
#include<vector>
#define inf 1<<30
using namespace std;
ifstream in("dijkstra.in"); ofstream out("dijkstra.out");
int use[50005],acum,a,b,c,n,m;
struct arc{ int u, c;}; //unde merge, cat costa
vector <arc> l[50005];
vector <int> d(50005, inf);
queue <int> q;
int main(){
    in>>n>>m;
    for(int i=1;i<=m;++i){ in>>a>>b>>c; l[a].push_back((arc){b,c});}
    d[1]=0;
    q.push(1);
    while(!q.empty()){
        acum=q.front(); q.pop();// use[acum]++;
       // if(use[acum]==n) return 0;
       vector <arc> :: iterator i=l[acum].begin(),sf=l[acum].end();
        for(; i!=sf;++i)
            if(d[(*i).u]>d[acum]+(*i).c){
                d[(*i).u]=d[acum]+(*i).c;
                q.push((*i).u);
            }
    }
    for(int i=2;i<=n;++i) out<<d[i]<<' ';
    out<<'\n';
    return 0;
}