///dijkstra pt orice nod sursa
#include <fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int N = 50005, M = 1999999999;
int d[N],poz[N],h[N];
struct nod{
    int nr,cost;
    nod *urm;
}*v[N];
void adaug(int x, int y, int z){
    nod *nou = new nod;
    nou->nr = y;
    nou->cost = z;
    nou->urm = v[x];
    v[x] = nou;
}
void up_heap(int f){
    while(f/2 && d[h[f]] < d[h[f/2]]){
        swap(h[f],h[f/2]);
        poz[h[f]] = f;
        poz[h[f/2]] = f/2;
        f /= 2;
    }
}
void down_heap(int t, int l){
    int f = 0;
    while(t != f){
        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 dijkstra(int ns, int n){
    int l = 0, rad, c, val;
    nod *nou = new nod;
    for(int i=1;i<=n;i++)
        d[i] = M;
    d[ns] = 0;
    poz[ns] = 1;
    h[++l] = ns;
    while(l){
        rad = h[1];
        swap(h[1],h[l--]);
        poz[h[1]] = 1;
        down_heap(1,l);
        nou = v[rad];
        while(nou){
            c = nou->cost;
            val = nou->nr;
            if(d[val] > d[rad] + c){
                d[val] = d[rad] + c;
                if(poz[val])
                    up_heap(poz[val]);
                else{
                    h[++l] = val;
                    poz[h[l]] = l;
                    up_heap(l);
                }
            }
            nou = nou->urm;
        }
    }
}
int main()
{
    int n,m,x,y,z,ns = 1;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        adaug(x,y,z);
    }
    in.close();
    dijkstra(ns,n);
    for(int i=1;i<=n;i++)
        if(i!=ns){
            if(d[i] != M)
                out<<d[i]<<" ";
            else
                out<<"0 ";
        }
    out<<"\n";
    out.close();
    return 0;
}