#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
#include <set>

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

#define v first
#define cost second

using namespace std;
const int inf=INT_MAX/2;
struct cmp{bool operator()(const pair<int,int>A,const pair<int,int>B)const{return A.cost<B.cost;}};
multiset<pair<int,int>,cmp>S;
vector<pair<int,int> >lv[50001];
vector<pair<int,int> >::iterator it;
int D[50001],T[50001],viz[50001],n,m;

void dijkstra()
{
    while(!S.empty())
    {
        int nodc=S.begin()->v;
        viz[nodc]=1;S.erase(S.begin());
        for(it=lv[nodc].begin();it!=lv[nodc].end();++it)
            if(D[it->v]>D[nodc]+it->cost)
            {
                D[it->v]=D[nodc]+it->cost;
                S.insert(make_pair(it->v,D[it->v]));
            }
    }
}

int main()
{
    fscanf(f,"%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;++i)
        fscanf(f,"%d%d%d",&a,&b,&c),lv[a].push_back(make_pair(b,c));
    for(int i=1;i<=n;++i)
        D[i]=inf;D[1]=0;
    S.insert(make_pair(1,0));dijkstra();
    for(int i=2;i<=n;++i)
        fprintf(g,"%d ",D[i]!=inf ? D[i]:0);
    return 0;
}