#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
const int N=50001;
const int inf=1<<31-1;

struct graf
{
    int nod,cost;
    graf *next;
};

int n,m,d[N],h[N],poz[N],k;
graf *a[N];

void add (int x,int y,int z)
{
    graf*q=new graf;
    q->nod=y;
    q->cost=z;
    q->next=a[x];
    a[x]=q;
}

void citire ()
{
    in>>n>>m;
    int x,y,z,i;
    for (i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        add (x,y,z);
    }
}

void swap (int x,int y)
{
    int aux;
    aux=h[x];
    h[x]=h[y];
    h[y]=aux;
}

void heapup(int x)
{
    int tata;
    while (x>1)
    {
        tata =x/2;
        if (d[h[tata]]>d[h[x]])
        {
            poz[h[x]]=tata;
            poz[h[tata]]=x;
            swap(tata,x);
            x=tata;
        }
        else x=1;
    }
}

void heapdown(int x)
{
    int f;
    while (x<=k)
    {
        f=x;
        if ((x/2)<=k)
        {
            f=x/2;
            if (f+1<=k)
                if (d[h[f+1]]<d[h[f]])
                    f++;
        }
        else return;

        if (d[h[x]]>d[h[f]])
        {
            poz[h[x]]=f;
            poz[h[f]]=x;

            swap(x,f);
            x= f;
        }
        else return;
    }
}

void dijkstra()
{
    int i,min;
    for (i = 2;i<= n;++i)
        {
        d[i] = inf;
        poz[i] = -1;
        }
    poz[1] = 1;
    h[++k] = 1;
    while (k)
    {
        min = h[1];
        swap(1,k);
        poz[h[1]]=1;
        k--;
        heapdown(1);
        graf *q=a[min];
        while (q)
        {
            if(d[q->nod]>d[min]+q->cost)
            {
                d[q->nod]=d[min]+q->cost;
                if (poz[q->nod]!=-1)
                    heapup(poz[q->nod]);
                else
                {
                    h[++k]=q->nod;
                    poz[h[k]]=k;
                    heapup(k);
                }
            }
            q=q->next;
        }
    }
}

int main()
{
    int i;
    citire();
    dijkstra();

    for (i=2; i<=n;i++)
        if (d[i]==inf) out<<0<<" ";
            else out<<d[i]<<" ";
        return 0;
}