#include <fstream>
#include<vector>
#include<queue>
#define INF 49999001
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nodul{
    int vf, c;
};

vector<nodul> a[50001];
int n,m,x,poz[50001],h[50001],nh,d[50001];

void schimba (int x, int y){
    int u=h[x];
    h[x]=h[y];
    h[y]=u;
    poz[h[x]]=x;
    poz[h[y]]=y;
}

void coboara(int i){
     int fs = 2*i, fd = 2*i + 1, bun = i;
    if (fs <= nh && d[h[fs]] < d[h[bun]])
        bun = fs;
    if (fd <= nh && d[h[fd]] < d[h[bun]])
        bun = fd;
    if (bun != i) {
        schimba(i, bun);
        coboara(bun);
    }
}
void sterg(int i){
    schimba(i,nh);
    nh--;
    coboara(1);
}


void urc(int i ){
    while(i>=2 && d[h[i]]<d[h[i/2]]){
        schimba(i,i/2);
        i/=2;
    }
}

void adaug(int x)
{
    h[++nh] = x;
    poz[x] = nh;
    urc(nh);
}

void dijkstra(int xnod){
    int y,cost;
    for (int i = 1; i <= n; i++)
            d[i] = INF;
    d[xnod] = 0;
    poz[1]=1;
    adaug(xnod);
    while(nh != 0){
        xnod=h[1];
        sterg(1);
        for(unsigned i=0;i<a[xnod].size(); i++){
            y = a[xnod][i].vf;
            cost = a[xnod][i].c;
            if(d[xnod] + cost < d[y]){
                d[y] = d[xnod] + cost;
                if (poz[y] == 0)
                    adaug(y);
                else
                    urc(poz[y]);
            }
        }
        //for (int i = 1; i <= nh; i++)
        //    g << "(" << h[i] << "," << d[h[i]] << ") " ;
        //g << "\n";
    }
}


int main()
{
    int i,na,nb,c;
    f>>n>>m;

    for(i=1;i<=m;i++){
        f>>na>>nb>>c;
        a[na].push_back((nodul){nb,c});
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
        if(d[i]==INF)
        g<<"0 ";
    else
        g<<d[i]<<" ";
    return 0;
}