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

using namespace std;

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

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

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

int main()
{

    //freopen("dijkstra.in","r",stdin);
    ifstream f("dijkstra.in");
    //freopen("grader_test10.in","r",stdin);
    freopen("dijkstra.out","w",stdout);


    //scanf("%d %d",&n,&m);
    f>>n>>m;


    for (i=1;i<=m;i++)
    {
        //scanf("%d %d %d",&x,&y,&c);
        f >> x>>y>>c;
        v[x].v.push_back(y);
        v[x].c.push_back(c);
    }

    a.push(1);
   // for (i=1;i<=n;i++)
   // cost[i]=999999999;

cost[1]=0;
    //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++)
        {
            //if (cost[v[k].v.at(i)]==0)
            if (cost[v[k].v.at(i)]==0 or cost[v[k].v.at(i)]>v[k].c.at(i)+cost[k])
            {
                if (v[v[k].v.at(i)].v.size()>0)
                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++)
    //if (cost[i]!=999999999)
    printf("%lld ",cost[i]);
    //else
    //printf("0 ");



    return 0;
}