#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n,m,k;
vector<int> v[50001],ds[50001];
int d[50001],h[50001],nd[50001],pz[50001];
bool ok[50001];

void sift(int x){

    int son;
    while(son){
        son=x*2;
        if(x*2+1<=k&&h[x*2+1]<h[son])
            son=x*2+1;

        if(h[x]<h[son])
            son=0;
        else{
            swap(h[x],h[son]);
            swap(nd[x],nd[son]);
            swap(pz[x],pz[son]);
        }
    }

    return;
}

int extract(){
    int ax=pz[1];
    if(k!=1) { nd[pz[k]]=1; nd[pz[1]]=k; swap(pz[1],pz[k]);}
    h[1]=h[k--];
    nd[pz[k+1]]=0;
    pz[k+1]=0; h[k+1]=0;

    if(k>1) sift(1);

    return ax;
}

void percolate(int x){
    int key=h[x];

    while(key<h[x/2]){
        swap(nd[x/2],nd[x]);
        swap(pz[x/2],pz[x]);
        h[x]=h[x/2];
        x/=2;
    }
    h[x]=key;
    return;
}

void insert(int x,int nod){
    nd[nod]=++k;
    pz[k]=nod;
    h[k]=x;

    percolate(k);
    return;
}

int main()
{
    f>>n>>m;

    for(int i=1;i<=m;i++){
        int x,y,c;
        f>>x>>y>>c;
        v[x].push_back(y);
        ds[x].push_back(c);
    }

    for(int i=1;i<=n;i++)
        d[i]=2000000000;
    d[1]=0;
    nd[1]=1;
    pz[1]=1;
    h[++k]=1;

    while(k){
        int x=extract();
        ok[x]=1;
        for(unsigned j=0;j<v[x].size();j++){
            if(!ok[v[x][j]]&&d[x]+ds[x][j]<d[v[x][j]]){
                d[v[x][j]]=d[x]+ds[x][j];
                if(nd[v[x][j]]){
                    h[nd[v[x][j]]]=d[v[x][j]];
                    percolate(nd[v[x][j]]);
                }else insert(d[v[x][j]],v[x][j]);
            }
        }
    }

    for(int i=2;i<=n;i++)
        g<< (d[i]==2000000000 ? 0 : d[i])<<" ";

    return 0;
}