#include <iostream>
#include <fstream>

using namespace std;

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

struct nod
{
    int info, d;
    nod * urm;
}*vecin[250001];

nod * prim[250001];

const long long INFINIT=5000000001;
const int MAX_HEAP_SIZE=50001;
typedef int heap[MAX_HEAP_SIZE];

inline int left_son (int x)
{
    return 2*x;
}

inline int right_son(int x)
{
    return 2*x+1;
}

inline int father (int x)
{
    return x/2;
}

heap h;
int p[50001];
long long d[50001];


void sift (heap h, int n, int k)
{
    int son;
    do
    {
        son=0;
        if(left_son(k)<=n)
        {
            son=left_son(k);

            if(right_son(k)<=n && h[right_son(k)] < h[left_son(k)])
            {
                son=right_son(k);
            }

            if(h[k] <= h[son])
            {
                son=0;
            }
        }

        if(son)
        {
            swap(p[ h[son] ], p[ h[k] ]);
            swap(h[son], h[k]);

            k=son;
        }
    }while(son);
}



void percolate (heap h, int n, int k)
{
    int key=h[k];

    while(k>1 && h[k]< h[father(k)])
    {
        p[ h[father(k)] ] = p[ h[k] ];
        h[k]=h[father(k)];

        k=father(k);
    }

    p[ key ]=k;
    h[k]=key;
}


int main()
{
    int n, m, i, a, b, c, l;
    fin>>n>>m;

    for(i=1; i<=m; i++)
    {
        fin>>a>>b>>c;

        //il adaug pe q la vecinii lui p
        nod * aux = new nod;
        aux->info=b;
        aux->d=c;
        aux->urm=NULL;

        if(prim[a]==NULL)
        {
            prim[a]=aux;
            vecin[a]=aux;
        }

        else
        {
            vecin[a]->urm=aux;
            vecin[a]=aux;
        }
    }

    h[1]=1;
    p[1]=1;
    d[1]=0;

    for(i=2; i<=n; i++)
    {
        p[i]=i;
        h[i]=i;
        d[i]=INFINIT;
    }

    l=n;
    for(i=1; i<n; i++)
    {
        int key=h[1];
        swap(p[ h[l] ], p[ h[1] ]);
        swap(h[l], h[1]);

        l--;

        sift(h, l, 1);

        nod * t = prim[key];
        while(t!=NULL)
        {
            if(d[key] + t->d < d[t->info])
            {
                d[t->info]=d[key] + t->d;
                percolate(h, l, p[t->info]);
            }
            t=t->urm;
        }
    }


    for(i=2; i<=n; i++)
    {
        if(d[i]!=INFINIT)fout<<d[i]<<' ';
        else fout<<0<<' ';
    }

}