#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)
{
    if(h.elems[poz].dist > h.elems[2*poz+1].dist ||
            h.elems[poz].dist > h.elems[2*poz+2].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;
    while(poz<(h.n/2) && !conditie_parinte(h,poz))
    {
        if(h.elems[poz].dist > h.elems[2*poz+1].dist ||
                h.elems[poz].dist > h.elems[2*poz+2].dist)
        {
            if(h.elems[2*poz+1].dist > h.elems[2*poz+2].dist)
            {
                swap(h.elems[poz],h.elems[2*poz+2]);
                poz=2*poz+2;
            }
            else
            {
                swap(h.elems[poz],h.elems[2*poz+1]);
                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;
    adauga(h,vf);
    while(h.n>0)
    {
        vector<varf> ::iterator it;
        for(it=v[h.elems[0].id].begin(); it!=v[h.elems[0].id].end(); it++)
        {

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

    for(int i=2; i<=n; i++)
        fo<<rez[i]<<" ";

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