#include <fstream>
#include <stdlib.h>
#define NM 50005
#define inf 1000000000

using namespace std;

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

void Citire();
void Initializare();
void Dijkstra();
void Afisare();

struct nod{int val, idx;};
struct lista{int nume, cost;};

int n, m;
lista *A[NM];

nod heap[NM];
int last=0;

int d[NM], loc[NM];

int main()
{
    Citire();
    Initializare();
    Dijkstra();
    Afisare();
    return 0;
}

void Citire()
{
    int i, x, y, c;
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        A[i] = (lista *) realloc(A[i], 2*sizeof(int));
        A[i][0].nume=0;
    }
    for (i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        A[x][0].nume++;
        A[x] = (lista *) realloc(A[x], (A[x][0].nume+1)*2*sizeof(int));
        A[x][A[x][0].nume].nume=y;
        A[x][A[x][0].nume].cost=c;
    }
}

void Initializare()
{
    int i;
    heap[0].val=inf;
    for (i=1; i<=n; i++)
        d[i]=inf;
    d[1]=0;
}

void Add(int who, int price)
{
    last++;
    int act=last;
    while (price < heap[act/2].val && act>1)
    {
        loc[heap[act/2].idx]=act;
        heap[act].val=heap[act/2].val;
        heap[act].idx=heap[act/2].idx;
        act=act/2;
    }
    heap[act].val=price;
    heap[act].idx=who;
    loc[who]=act;
}

void Edit(int place, int update, int who)
{
    int act=place;
    while (update < heap[act/2].val && act>1)
    {
        loc[heap[act/2].idx]=act;
        heap[act].val=heap[act/2].val;
        heap[act].idx=heap[act/2].idx;
        act=act/2;
    }
    heap[act].val=update;
    heap[act].idx=who;
    loc[who]=act;
}

int Pop()
{
    int a, b;
    nod imp=heap[last];
    int deretur=heap[1].idx;
    loc[heap[1].idx]=0;
    heap[last].idx=0;
    heap[last].val=0;
    last--;
    int act=1;
    while ((heap[act*2+1].val<imp.val && heap[act*2+1].val>0) || (heap[act*2].val<imp.val && heap[act*2].val>0))
    {
        a=heap[act*2].val;
        b=heap[act*2+1].val;
        if (a>0 && b>0)
        {
            if (a>b)
            {
                loc[heap[act*2+1].idx]=act;
                heap[act]=heap[act*2+1];
                act=act*2+1;
            }
            else
            {
                loc[heap[act*2].idx]=act;
                heap[act]=heap[act*2];
                act=act*2;
            }

        }
        else
        {
            if (a>0)
            {
                loc[heap[act*2].idx]=act;
                heap[act]=heap[act*2];
                act=act*2;
            }
            else
            {
                loc[heap[act*2].idx]=act;
                heap[act]=heap[act*2];
                act=act*2;
            }
        }
    }
    heap[act]=imp;
    loc[imp.idx]=act;
    return deretur;
}

void Dijkstra()
{
    int i, p, c, x=1;
    while (x!=0)
    {
        for (i=1; i<=A[x][0].nume; i++)
        {
            p=A[x][i].nume;
            c=A[x][i].cost;
            if (p==2)
                int aci=2;
            if (d[p]==inf)
            {
                d[p]=c+d[x];
                Add(p, c+d[x]);
            }
            else
            {
                if (d[p]>c+d[x])
                {
                    d[p]=c+d[x];
                    Edit(loc[p], c+d[x], p);
                }
            }
        }
        x=Pop();
    }
}

void Afisare()
{
    int i;
    for (i=2; i<=n; i++)
    {
        if (d[i]==inf)
            fout<<0<<" ";
        else
            fout<<d[i]<<" ";
    }
}