#include <fstream>
#include <vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int N = 50002, M = 1999999999;
int h[N], poz[N], d[N];
vector < pair<int, int> > v[N];
void upHeap(int f){
    while(f/2 && d[h[f/2]] > d[h[f]]){
        swap(h[f],h[f/2]);
        poz[h[f]] = f;
        poz[h[f/2]] = f/2;
        f /= 2;
    }
}
void downHeap(int t, int l){
    int f = 0;
    while(f != t){
        f = t;
        if(f*2 <= l && d[h[t]] > d[h[f*2]])
            t = f*2;
        if(f*2+1 <= l && d[h[t]] > d[h[f*2+1]])
            t = f*2+1;
        swap(h[t],h[f]);
        poz[h[t]] = t;
        poz[h[f]] = f;
    }
}
void insertHeap(int val, int &l){
    h[++l] = val;
    poz[val] = l;
    upHeap(l);
}
int extractHeap(int &l){
    int rad = h[1];
    poz[rad] = 0;
    swap(h[1],h[l--]);
    poz[h[1]] = 1;
    downHeap(1,l);
    return rad;
}
void dijkstra(int ns, int n){
    int l = 0, sz, rad, c, nbr;
    for(int i=1;i<=n;i++)
        d[i] = M;
    d[ns] = 0;
    insertHeap(ns,l);
    while(l > 0){
        rad = extractHeap(l);
        sz = v[rad].size();
        for(int i=0;i<sz;i++){
            nbr = v[rad][i].first;
            c = v[rad][i].second;
            if(d[nbr] > d[rad] + c){
                d[nbr] = d[rad] + c;
                if(poz[nbr])
                    upHeap(poz[nbr]);
                else
                    insertHeap(nbr,l);
            }
        }
    }
}
int main()
{
    int n,m,x,y,z;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    in.close();
    dijkstra(1,n);
    for(int i=2;i<=n;i++)
        if(d[i] != M)
            out<<d[i]<<" ";
        else
            out<<"0 ";
    out.close();
    return 0;
}