#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

int n,m,i,j,l,x,y,c,p,u,k;

struct abc
{
    vector<int> v;
    vector<int> c;
} v[50040];

queue<int> a;
long long cost[50001];

int main()
{

    //freopen("dijkstra.in","r",stdin);
    freopen("grader_test10.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);
        v[x].v.push_back(y);
        v[x].c.push_back(c);
    }

    a.push(1);
    cost[1]=0;

    for (i=1;i<=n;i++)
    cost[i]=999999999;

    //printf("ajunge");

    while (a.size()>0)
    {
        k=a.front();
        a.pop();
       //printf("%d\n",v[a[p]].v.size());
        for (i=0;i<v[k].v.size();i++)
        {
            //cost[v[k].v.at(i)]==0 or
            if ( cost[v[k].v.at(i)]>v[k].c.at(i)+cost[k])
            {

                a.push(v[k].v.at(i));
                cost[v[k].v.at(i)]=v[k].c.at(i)+cost[k];
            }
        }



    }

    for (i=2;i<=n;i++)
    printf("%ld ",cost[i]);



    return 0;
}