#include<fstream>
#define inf "dijkstra.in"
#define outf "dijkstra.out"
#define NMax 50010
#define INF 0x3f3f3f3f
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

struct graf
{
int nod,cost;
graf *next;
};

int N,M;
graf *a[NMax];//lista de adiacenta
int d[NMax];
int heap[NMax];//heap[i]=j <=> eticheta nodului i din heap este nodul j din graf
int pos[NMax];//pos[i]=j <=> nodul i din graf este eticheta nodului j din heap
int dim;//numarul de noduri din heap la un moment dat

void add(int unde,int nd,int costarc)//adaug in lista de adiacenta a nodului unde, nodul nd
{
graf *c=new graf;
c->nod=nd;
c->cost=costarc;
c->next=a[unde];
a[unde]=c;
}

void Citire()//citesc datele
{
int x,y,z;
f>>N>>M;
for(int i=1;i<=M;i++)
    {
    f>>x>>y>>z;
    add(x,y,z);
    }
for(int i=1;i<=N;i++){d[i]=INF;pos[i]=-1;}//initializez vectorul d cu INF(0x3f3f3f3f)
}

int father(int nodh){return nodh/2;}//tatal nodului nodh din heap
int lson(int nodh){return nodh*2;}//fiul stang al nodului nodh din heap
int rson(int nodh){return nodh*2+1;}//fiul drept al nodului nodh din heap

void upheap(int nodh)//"ridic" nodul nodh in heap
{
int tata;
tata=father(nodh);
while(tata>1)
    {
    if(d[heap[nodh]]<d[heap[tata]])
        {
        swap(pos[heap[nodh]],pos[heap[tata]]);
        swap(heap[nodh],heap[tata]);
        nodh=tata;
        tata=father(nodh);
        }
    else break;
    }
}

void downheap(int nodh)//"cern" nodul nodh in heap
{
int son=0;
do
    {
    son=0;
    if(lson(nodh)<=dim)
        {
        son=lson(nodh);
        if(rson(nodh)<=dim && d[heap[son]]>d[heap[rson(nodh)]])son=rson(nodh);
        if(d[heap[son]]<d[heap[nodh]])
            {
            swap(pos[heap[son]],pos[heap[nodh]]);
            swap(heap[son],heap[nodh]);
            nodh=son;
            }
        else son=0;
        }
    }
while(son);
}

void cut(int nodh)
{
swap(pos[heap[nodh]],pos[heap[dim]]);
swap(heap[nodh],heap[dim]);
dim--;
if(dim>0)downheap(nodh);
//"cernem" nodul,fara sa il "urcam", deoarece procedura cut va fi apelata doar pentru primul nod din heap
}

void insert(int nodg)//inseram in heap nodul din graf (nodg)
{
heap[++dim]=nodg;
pos[nodg]=dim;
upheap(dim);
}

void Dijkstra()
{
int min;
d[1]=0;
pos[1]=1;
heap[++dim]=1;
while(dim)
    {
    min=heap[1];
    cut(1);
    graf *t=a[min];
    while(t)
        {
        if(d[t->nod]>d[min]+t->cost)
            {
            d[t->nod]=d[min]+t->cost;
            if(pos[t->nod]!=-1)upheap(pos[t->nod]);
            else insert(t->nod);
            }
        t=t->next;
        }
    }
}

void Afisare()
{
for(int i=2;i<=N;i++)
    {
    if(d[i]==INF)g<<"0 ";
    else g<<d[i]<<" ";
    }
}

int main()
{
Citire();
Dijkstra();
Afisare();
f.close();
g.close();
return 0;
}