#include "cstdio"
#include "fstream"
#include "vector"
#define fin "dijkstra.in"
#define fout "dijkstra.out"
#define inf 0x3f3f3f3f
#define nMax 50010
using namespace std;

    typedef struct drum { int x,c; };

    int n,m,d[nMax];
    vector<drum> G[nMax];

class minheap
{
    public: int heap[3*nMax],dpt;

    public: void push(int x) // Push in heap nodul x
    {
        heap[++dpt]=x;
        int poz=dpt;
        int padre;
        while (poz >1)
        {
            padre = poz>>1;
            if (d[heap[padre]]>d[heap[poz]])
            {
                int aux=heap[padre]; heap[padre]=heap[poz]; heap[poz]=aux;
            }
            poz=padre;
        }
    }

    public: int pop() // Scoate min si rebalanseaza heapul
    {
        int rez=heap[1];
        heap[1]=heap[dpt--];
        int nod=1;
        int son=0;
        if (2<=dpt && d[heap[2]]<d[heap[1]])
            son=2;
        if (3<=dpt && d[heap[3]]<d[heap[2]] && son==2)
            son=3;
        while(d[heap[nod]]>d[heap[son]] && son!=0)
        {
            int aux=heap[nod]; heap[nod]=heap[son]; heap[son]=aux;
            nod=son;
            son=0;
            int dr=2*nod,st=2*nod+1;
            if (dr<=dpt &&d[heap[dr]]<d[heap[nod]])
                son=dr;
            if (st<=dpt &&d[heap[st]]<d[heap[dr]] && son==dr)
                son=st;
        }
        return rez;
    }
};

    minheap hip;

void citire()
{
    ifstream input(fin);
    input>>n>>m;
    for (int i=0;i<m;i++)
    {
        int x,y,z;
        input>>x>>y>>z;
        drum d; d.x=y; d.c=z;
        G[x].push_back(d);
    }
    input.close();
}


void build_heap()
{
    for (int i=2;i<=n;i++)
        d[i]=inf;
    for (vector<drum>::iterator it = G[1].begin(); it != G[1].end(); it ++)
        d[it->x]=it->c;
    for (int i=2;i<=n;i++)
        hip.push(i);
}

void dijkstra() // Dijkstra
{
    while (hip.dpt>=0) // cat timp mai avem varfuri in heap
    {
        int vs=hip.pop();
        for (vector<drum>::iterator it = G[vs].begin(); it != G[vs].end(); it ++)
            if (d[it->x] > d[vs]+it->c && it->x != 1) // Imbunatatire drum
            {
                d[it->x] = d[vs]+it->c;
                hip.push(it->x);
            }
    }
}
int main()
{
    citire();
    build_heap();
    dijkstra();
    freopen(fout,"w",stdout);
    for (int i=2;i<=n;i++)
            printf("%d ",d[i]==inf ? 0 : d[i]);
	return 0;
}