#include<stdio.h>
#include<set>
#include<vector>
#define Nmax 50002
#define inf 0x3f3f3f3f
using namespace std;
int n,m,d[Nmax],viz[Nmax];

multiset< pair < int, pair < int,int > > > h;
vector< pair < int,int > > g[Nmax];

void citire()
{
    int i,x,y,c;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }
}

void dijkstra()
{
    int i,c,x,y;
    vector< pair < int,int > >::iterator it;
    for(i=1;i<=n;++i)
        d[i]=inf;
    for(it=g[1].begin();it!=g[1].end();++it)
        h.insert(make_pair(it->second,make_pair(1,it->first)));
    d[1]=0;
    viz[1]=1;
    for(i=1;i<n;++i)
    {
        c=h.begin()->first;
        x=h.begin()->second.first;
        y=h.begin()->second.second;
        h.erase(h.begin());
        viz[y]=1;
        d[y]=d[x]+c;
        for(it=g[y].begin();it!=g[y].end();++it)
        {
            x=it->first;
            c=it->second;
            if(viz[x]==0 && d[y]+c < d[x])
                h.insert(make_pair(c,make_pair(y,x)));
        }
    }
}

void scrie()
{
    int i;
    for(i=2;i<=n;++i)
        printf("%d ",d[i]);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    scrie();
    fclose(stdin);
    fclose(stdout);
    return 0;
}