#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define L 50005
#define oo 0x3f3f3f
#define pb push_back

using namespace std;

int Dist[L];

struct cmp
{
    bool operator ()(const int &a, const int &b)const
    {
        return Dist[a] > Dist[b];
    }
};

priority_queue <int , vector <int>, cmp> Q;

struct nod
{
    int i,d;
    nod *next;
}*V[L];

bool viz [L];

int n, m, a, b, c;

void add(nod *&X, int a,int b)
{
    nod *q=new nod;
    q->i=a;
    q->d=b;
    q->next=X;
    X=q;
}

void citire()
{
    scanf ("%d %d ", &n, &m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d %d",&a,&b,&c);
        add(V[a], b, c);
    }
}

void dijkstra()
{
    int Top, D, no, dis;

    for (int i=2;i<=n;i++)
        Dist[i]=oo;

    Q.push(1);

    while(!Q.empty())
    {
        Top=Q.top();
        Q.pop();
        viz[Top]=false;
        D=Dist[Top];
        for (nod *q=V[Top];q;q=q->next)
        {
            no=q->i;
            dis=q->d;
            if (D + dis < Dist[no])
            {
                Dist[no]=D+dis;
                if (!viz[no])
                {
                    viz[no]=true;
                    Q.push(no);
                }
            }
        }
    }
}

void afisare()
{
    for (int i=2;i<=n;i++)
        printf("%d ",Dist[i]==oo?0:Dist[i]);
}

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);
    citire();
    dijkstra();
    afisare();
    return 0;
}