#include <iostream>
#include <fstream>
#include <vector>
#define INF 9999999

using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

struct varf
{
    int id, dist;
};

struct heap
{
    int n;
    varf elems[50001];
};

heap creeaza_heap()
{
    heap h;
    h.n=0;
    return h;
}

bool conditie_copil(heap h, int poz)
{
    if(h.elems[(poz-1)/2].dist > h.elems[poz].dist)
        return false;
    return true;
}

bool conditie_parinte(heap h, int poz)
{
    int c1,c2;
    c1=c2=2*poz+1;
    if(c1+1<h.n)
        c2=c1+1;
    if(h.elems[poz].dist > h.elems[c1].dist ||
            h.elems[poz].dist > h.elems[c2].dist)
        return false;
    return true;
}

void heapify_up(heap& h, int poz)
{
    while(poz>0 && (!conditie_copil(h,poz)))
    {
        swap(h.elems[poz], h.elems[(poz-1)/2]);
        poz=(poz-1)/2;
    }
}

void adauga(heap& h, varf vf)
{
    h.elems[h.n]=vf;
    h.n++;
    heapify_up(h, h.n -1);
}

varf sterge(heap& h)
{
    varf rez=h.elems[0];
    h.n--;
    h.elems[0]=h.elems[h.n];
    int poz=0;
    int c1,c2;
    while(poz<(h.n/2) && !conditie_parinte(h,poz))
    {
        c1=c2=2*poz+1;
        if(c1+1<h.n)
            c2=c1+1;

        if(h.elems[c1].dist > h.elems[c2].dist)
        {
            swap(h.elems[poz],h.elems[c2]);
            poz=2*poz+2;
        }
        else
        {
            swap(h.elems[poz],h.elems[c1]);
            poz=2*poz+1;
        }
    }
    return rez;
}

int n, m;
vector<varf> v[50001];
int rez[50001];

int main()
{
    fi>>n>>m;
    for(int i=1; i<=n; i++)
        rez[i]=INF;
    int a,b,c;
    varf vf;
    for(int i=1; i<=m; i++)
    {
        fi>>a>>b>>c;
        vf.id=b;
        vf.dist=c;
        v[a].push_back(vf);
        /*vf.id=a;
        v[b].push_back(vf);*/
    }

    heap h= creeaza_heap();
    vf.id=1;
    vf.dist=0;
    rez[1]=0;
    varf rad;
    adauga(h,vf);
    while(h.n>0)
    {
        vector<varf> ::iterator it;
        rad=sterge(h);
        for(it=v[rad.id].begin(); it!=v[rad.id].end(); it++)
        {

            vf.id=(*it).id;
            vf.dist=(*it).dist+rad.dist;
            if(rez[vf.id]>vf.dist)
            {
                rez[vf.id]=vf.dist;
                adauga(h,vf);
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
        if(rez[i]==INF)
            rez[i]=0;
        fo<<rez[i]<<" ";
    }

    fi.close();
    fo.close();
    return 0;
}