#include <fstream>
#include <vector>
#define NMAx 50100
#define inf (1<<28)
#define left(i) (2*i)
#define right(i) (2*i+1)
#define father(i) (i/2)
#define cmp(a,b) (dist[heap[a]]<dist[heap[b]])
using namespace std;
vector <unsigned short> G[NMAx],Cost[NMAx];
int n,vf=1,heap[NMAx],dist[NMAx],loc[NMAx];
 
void up(int nod) {
     
    while(nod>1&&cmp(nod,father(nod))) {
        swap(heap[nod],heap[father(nod)]);
        swap(loc[heap[nod]],loc[heap[father(nod)]]);
        nod=father(nod);
        }
     
}
void down(int nod) {
     
    int son;
    do {
        son=0;
        if(left(nod)<=vf) {
            son=left(nod);
            if(right(nod)<=vf&&cmp(right(nod),left(nod)))
                son=right(nod);
            if(cmp(nod,son))
                son=0;
            }
        if(son) {
            swap(heap[nod],heap[son]);
            swap(loc[heap[nod]],loc[heap[son]]);
            nod=son;
            }
    }while(son);
     
}
void dijkstra() {
    int nod,vecin,i;
    heap[1]=1;
    loc[1]=1;
    while(vf) {
        nod=heap[1];
        loc[nod]=-1;
        heap[1]=heap[vf--];
        loc[heap[1]]=1;
        down(1);
        for(i=0;i<G[nod].size();i++) {
            vecin=G[nod][i];
            if(!loc[vecin]) {
                heap[++vf]=vecin;
                loc[vecin]=vf;
                dist[vecin]=dist[nod]+Cost[nod][i];
                up(loc[vecin]);
                }
            else
            if(dist[vecin]>dist[nod]+Cost[nod][i]) {
                dist[vecin]=dist[nod]+Cost[nod][i];
                up(loc[vecin]);
                }
            }
        }
}
void citire() {
     
    int i,x,y,c,m;
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(i=0;i<m;i++) {
        in>>x>>y>>c;
        G[x].push_back(y);
        Cost[x].push_back(c);
        }
    in.close();
     
}
void afis() {
 
    int i;
    ofstream out("dijkstra.out");
    for(i=2;i<=n;i++)
    if(dist[i]==inf)
        out<<"0 ";
    else
        out<<dist[i]<<' ';
    out<<'\n';
    out.close();
     
}
int main() {
     
    citire();
    dijkstra();
    afis();
 
    return 0;
     
}