#include<fstream>
#include<vector>
#define INF 1 << 25
#define maxN 50005
using namespace std;
 
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
 
int N,M,i,x,y,D[maxN],Poz[maxN];
int L,H[maxN];
 
struct mch{
    int nod;
    int cst;
}aux;
 
vector<mch>A[maxN];
 
void urca(int poz){
    while ( poz != 0 && D[ H[poz/2] ] > D[ H[poz] ] ){
        swap(H[poz],H[poz/2]);
        swap(Poz[H[poz]],Poz[H[poz/2]]);
        poz = poz >> 1;
    }
}
 
void coboara(int x){
    int y = 0;
     
    while ( x != y ){
        y = x;
        if ( (y << 1) <= L && D[H[ y << 1 ]] < D[H[ x ]] )
            x = y << 1;
        if ( (y << 1) + 1 <= L && D[H[(y<<1)+1]] < D[H[ x ]] )
            x = ( y << 1 ) + 1;
        swap(H[x],H[y]);
        swap(Poz[H[x]],Poz[H[y]]);
    }
     
}
 
void delete_heap(){
    H[1] = H[L--]; Poz[H[1]] = 1;
    coboara(1);
}
 
int main () {
    f >> N >> M;
    for ( i = 1 ; i <= M ; ++i ){
        f >> x >> aux.nod >> aux.cst;
        A[x].push_back(aux);
    }
     
    for ( i = 2 ; i <= N ; ++i )
        D[i] = INF;
     
    ++L;
    H[1] = 1; Poz[H[1]] = 1;
     
    while ( L ){
        int nod = H[1];
        delete_heap();
         
        for ( i = 0 ; i < A[nod].size() ; ++i ){
            int nd = A[nod][i].nod;
            int cst = A[nod][i].cst;
            if ( D[nod] + cst < D[nd] ){
                D[nd] = D[nod] + cst;
                if ( Poz[nd] ){
                    urca(Poz[nd]);
                }
                else{
                    ++L;
                    H[L] = nd; Poz[H[L]] = L;
                    urca(L);
                }
            }
             
        }
    }
     
    for ( i = 2 ; i <= N ; ++i ){
        if ( D[i] == INF )
            g << "0 ";
        else
            g << D[i] << " ";
    }
     
    f.close();
    g.close();
     
    return 0;
}