///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;
}
bool cobor(int t, int l){
    int f;
    while(t <= l){
        f = t;
        if(t*2 <= l){
            f = t*2;
            if(f+1 <=l && d[h[f+1]] < d[h[f]])
                f++;
            if(d[h[t]] > d[h[f]]){
                poz[h[t]] = f;
                poz[h[f]] = t;
                swap(h[f],h[t]);
                t = f;
            }
            else
                return false;
        }
        else
            return false;
    }
    return false;
}
void urc(int f){
    int t;
    while(f > 1){
        t = f/2;
        if(d[h[t]] > d[h[f]]){
            poz[h[f]] = t;
            poz[h[t]] = f;
            swap(h[f],h[t]);
            f = t;
        }
        else
            f = 1;
    }
}
void dijkstra(int ns, int n){
    int l = 0, rad, c, val;
    nod *nou = new nod;
    for(int i=1;i<=n;i++)
        if(i!=ns)
            d[i] = M;
    poz[ns] = 1;
    h[++l] = ns;
    while(l){
        rad = h[1];
        swap(h[1],h[l--]);
        poz[h[1]] = 1;
        cobor(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])
                    urc(poz[val]);
                else{
                    h[++l] = val;
                    poz[h[l]] = l;
                    urc(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;
}