#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 sterg(int i){
    schimba(i,nh);
    nh--;
}

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;
    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]);
            }
        }
    }
}


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++)
        g<<d[i]<<" ";
    return 0;
}