#include <iostream>
#include <fstream>
#define  maxint 2147483647

using namespace std;

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

struct node
{
    int x,k;
    node *kov;
};

int latott[50001], kolt[50001], honnan[50001];
int n,m,x,y,k;

node *v[50001];

int inic()
{
    for(int i=1;i<=n;i++)
    {
        latott[i]=0;
        kolt[i]=maxint;
        honnan[i]=0;
    }
    return 0;
}

int betesz()
{
    node *p;
    p=new node;
    p->x=y;
    p->k=k;
    p->kov=v[x];
    v[x]=p;
    /*p=new node;
    p->x=x;
    p->k=k;
    p->kov=v[y];
    v[y]=p;*/
    return 0;
}

int keres()
{
    int pp=-1,min=maxint;
    for(int i=1;i<=n;i++)
    {
        if(latott[i]==0&&kolt[i]<min)
        {
            pp=i;
            min=kolt[pp];
        }
    }
    return pp;
}

int main()
{
    fin>>n>>m;
    inic();
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>k;
        betesz();
    }
    for(int i=1;i<=n;i++)
    {
        cout<<i<<" ";
        node *p=v[i];
        while(p!=NULL)
        {
            cout<<p->x<<" ";
            p=p->kov;
        }
        cout<<"\n";
    }
    kolt[1]=0;
    honnan[1]=0;
    int poz=keres();
    while(poz!=-1)
    {
        latott[poz]=1;
        node *p=v[poz];
        while(p!=NULL)
        {
            if(latott[p->x]==0&&kolt[p->x]>kolt[poz]+p->k)
            {
                kolt[p->x]=kolt[poz]+p->k;
                honnan[p->x]=poz;
            }
            p=p->kov;
        }
        poz=keres();
    }

    for(int i=2;i<=n;i++)
        if(kolt[i]!=maxint) fout<<kolt[i]<<" ";
        else fout<<0<<" ";
    return 0;
}