#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#define mm 250001
#define nm 50001
#define mx 1000000001

using namespace std;

struct s2{int y,c;} nod,nn;

bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.second<b.second;
}

struct comp
{
    bool operator()(s2 i,s2 j) const{
    return i.c<j.c;}
};


int i,j,n,m,x,y,c,C[nm];
vector <pair<int,int> > g[nm];
multiset <s2, comp> unv;

void dj(s2 k)
{
    int j;
    for(j=0;j<g[k.y].size();j++)
    {
        if(C[k.y]+g[k.y][j].second<C[g[k.y][j].first])
        {
            C[g[k.y][j].first]=C[k.y]+g[k.y][j].second;
            nod.y=g[k.y][j].first; nod.c=C[g[k.y][j].first];
            unv.insert(nod);
        }
    }
    set<s2, comp>::iterator it=unv.find(k);  unv.erase(it);
    if(unv.empty()) return;
    nod=*unv.begin(); dj(nod);
}

int main()
{

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    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));
    }
    for(i=1;i<=n;i++) stable_sort(g[i].begin(),g[i].begin()+g[i].size(),cmp);
    nod.y=1; nod.c=0; unv.insert(nod);
    for(i=2;i<=n;i++) {C[i]=mx; nod.y=i; nod.c=mx; unv.insert(nod);}
    nod.y=1; nod.c=0; dj(nod); for(i=2;i<=n;i++) printf("%d ",C[i]%mx);
    return 0;
}