#include <fstream>
#include <vector>
#define maxn 50000
#define inf 1234567


using namespace std;

 int N,M, dist[maxn+100],poz[maxn+100], edges[maxn*5+100][3], heap[maxn*2+100][2], hind;
    vector<int> vecini[maxn];
inline  void swap(int i, int j)
{
int z[2];

    z[0]=heap[i][0];
    z[1]=heap[i][1];
    heap[i][0]=heap[j][0];
    heap[i][1]=heap[j][1];
    heap[j][0]=z[0];
    heap[j][1]=z[1];
    int t=poz[i];
    poz[i]=poz[j];
    poz[j]=t;

}
inline void upheap(int);
inline void add(int i) {
    heap[++hind][0]=dist[i];
    heap[hind][1]=i;
    upheap(hind);
    poz[i]=hind;
}
inline int edist(int a,int b) {
    for (int i=0;i<M;i++)
    {
        if (edges[i][0]==a&&edges[i][1]==b) return edges[i][2];
    }
    return inf;
}
inline void dellete(int i) {
    heap[i][0]=heap[hind][0];
    heap[i][1]=heap[hind][1];
    poz[hind]=i;
    heap[hind][0]=0;
    heap[hind][1]=0;
    hind--;
}
inline void upheap(int i) {
    while (i/2>0&&heap[i][0]<heap[i/2][0])
    {
        swap(i,i/2);
        i/=2;
    }
}
inline void downheap(int i) {
    while ((2*i<=hind&&heap[i][0]>heap[2*i][0])||(2*i+1<=hind&&heap[i][0]>heap[2*i+1][0]))
    {
        if (2*i<=hind&&2*i+1>hind)
         {
             swap(i,2*i);
             i*=2;
         }
         else
        if (heap[2*i+1]<heap[2*i])
         {
             swap(2*i+1,i);
             i=2*i+1;
         }
         else
         {
             swap(2*i,i);
             i=2*i;
         }
    }
}
int main () {
    ifstream in;
    ofstream out;
    in.open("dijkstra.in");
    out.open("dijkstra.out");
    in >> N >> M;
    for (int i=0; i<M; i++) {
       in >> edges[i][0] >> edges[i][1] >> edges[i][2];
       vecini[edges[i][0]].push_back(edges[i][1]);
    }
    dist[1]=0;
    add(1);
    for (int i=2; i<=N; i++)
    {
        dist[i]=inf;
        //dist[i]=i;
        add(i);
    }
    while (hind!=0) {
        int u=heap[1][1];
        dellete(1);
        vector<int>::iterator it;
        for (it=vecini[u].begin();it!=vecini[u].end();it++) {
            int v=*it;
            int alt=dist[u]+edist(u,v);
            if (alt<dist[v]) {
                dist[v]=alt;
                heap[poz[v]][0]=alt;
                upheap(poz[v]);
            }
        }
    }
    for (int i=2; i<=N; i++)
    out << dist[i] << " ";
    out.close();
    return 0;
}