#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

int c_mod(int a, int b)
{
    if(a%b>=0)return a%b;
    return a%b+b;
}

int c_div(int a, int b)
{
    if(a%b>=0)return a/b;
    return a/b-1;
}

int h[50003],hs,d[50003],prez[50003];

void swp(int a,int b)
{
    prez[h[a]]=b;
    prez[h[b]]=a;
    int aux=h[a];
    h[a]=h[b];
    h[b]=aux;
}

int comp(int a,int b)
{
    if(d[h[a]]<=d[h[b]])return 1;
    return 0;
}

void act(int a)
{
    while(a>1)
    {
        if(comp(a/2,a)==0)swp(a,a/2);
        else break;
        a/=2;
    }
}

void del(int a)
{
    prez[h[a]]=0;
    h[a]=0;
    int b,c;
    while(a*2+1<=hs)
    {
        b=a*2;
        c=b+1;
        if(comp(b,c)==1)
        {
            swp(a,b);
            a=b;
        }
        else
        {
            swp(a,c);
            a=c;
        }
    }
    if(a*2<=hs)
    {
        swp(a,a*2);
        a*=2;
    }
    swp(a,h[hs]);
    if(a<hs)act(a);
    hs--;
}

struct lst
{
    int id,dst;
    lst *urm;
}*vp[50003],*vu[50003],*u;

int n,m,i,j,k,l;

fstream f,g;

int main()
{
    f.open("dijkstra.in",ios_base::in);
    g.open("dijkstra.out",ios_base::out);
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>l;
        u=new lst;
        u->id=k;
        u->dst=l;
        u->urm=NULL;
        if(vp[j]==NULL)vp[j]=u;
        else vu[j]->urm=u;
        vu[j]=u;
    }
    prez[1]=-1;
    for(hs=0,u=vp[1];u!=NULL;u=u->urm,hs++)
    {
        h[hs+1]=u->id;
        d[u->id]=u->dst;
        prez[u->id]=hs+1;
        act(hs+1);
    }
    while(hs>0)
    {
        for(i=1;i<=hs;i++)cout<<h[i]<<"->"<<d[h[i]]<<"  ";
        cout<<'\n';
        for(u=vp[h[1]];u!=NULL;u=u->urm)
        {
            if(prez[u->id]!=0&&prez[u->id]!=-1)
            {
                d[u->id]=min(d[u->id],u->dst+d[h[1]]);
                act(prez[u->id]);
            }
            else if(prez[u->id]!=-1)
            {
                hs++;
                h[hs]=u->id;
                prez[u->id]=hs;
                d[u->id]=u->dst+d[h[1]];
                act(hs);
            }
        }
        del(1);
    }
    for(i=2;i<=n;i++)g<<d[i]<<' ';
}