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

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

priority_queue< pair <int,int> , vector < pair <int,int> > , cmp> Q;
vector< pair <int,int> > lv[50001];
vector< pair <int,int> > ::iterator it;

int n,m,D[50001],viz[50001];

void dykstra(int k)
{
    while(!Q.empty())
    {
        k=Q.top().v;
        viz[k]=1;
        Q.pop();
        for(it=lv[k].begin();it!=lv[k].end();++it)
            if(D[(*it).v]>D[k]+(*it).cost&&!viz[(*it).v]) {
                D[(*it).v]=D[k]+(*it).cost;
                Q.push(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=2;i<=n;++i)D[i]=inf;
    Q.push(make_pair(1,0));
    dykstra(1);
    for(int i=2;i<=n;++i)
        if(D[i]!=inf)fprintf(g,"%d ",D[i]);
        else fprintf(g,"0 ");
    return 0;
}