#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int N,M,d[50001],A,B,c;
vector <int> Gx[250001],C[250001];
queue <int> coada;
int main(){
    f>>N>>M;
    for(int i=1;i<=M;++i){
        f>>A>>B>>c;
        Gx[A].push_back(B);
        C[A].push_back(c);
    }
    for(int i=1;i<=N;++i)
        d[i]=0x3f3f3f3f;
    d[1]=0;
    coada.push(1);
    while(!coada.empty()){
        int x=coada.front();
        coada.pop();
        for(int i=0;i<Gx[x].size();++i)
            if(d[Gx[x][i]]>d[x]+C[x][i]){
                d[Gx[x][i]]=d[x]+C[x][i];
                coada.push(Gx[x][i]);
            }
    }
    for(int i=2;i<=N;++i)g<<d[i]<<' ';
    return 0;
}