#include <iostream>
#include <fstream>

#define dim 50001

using namespace std;

const int inf = 2000000000; ///infinit

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct graf
{
    int y,len;
    graf* next;
}*a[dim];

int n,m;
bool s[dim];

int main()
{
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        graf* nou=new graf;
        nou->y=y;
        nou->len=cost;
        nou->next=a[x];
        a[x]=nou;
    }
    int d[dim],t[dim];
    d[1]=0;
    for (int i=2; i<=n; i++)
        d[i]=inf;
    graf* i=a[1];
    while(i!=NULL)
    {
        d[i->y]=i->len;
        t[i->y]=1;
        i=i->next;
    }
    s[1]=true;
    while (true)
    {
        int mini=inf,nodcurent;
        for (int i=1; i<=n; i++)
            if (d[i]<mini&&s[i]==false)
            {
                mini=d[i];
                nodcurent=i;
            }
        if (mini==inf)
            break;
        s[nodcurent]=true;
        graf* j=a[nodcurent];
        while (j!=NULL)
        {
            if (d[nodcurent]+j->len<d[j->y])
            {
                d[j->y]=d[nodcurent]+j->len;
                t[j->y]=nodcurent;
            }
            j=j->next;
        }
    }
    for (int i=2; i<=n; i++)
        fout<<d[i]<<' ';
    return 0;
}