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


using namespace std;

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

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

int a[2000000],cost[50001];

int main()
{

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);


    scanf("%d %d",&n,&m);

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


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

    u=1;
    p=1;
    a[1]=1;
    cost[1]=0;

    //printf("ajunge");

    while (p<=u)
    {

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

        p++;

    }

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



    return 0;
}