#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int a[5000][5000],d[5000],s[5000],t[5000];
long n,m,r;
const unsigned int INF=1001;
void cit()
 {
    int i,j,c;
        fin>>n>>m;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i!=j)
                    a[i][j]=INF;
    while(fin>>i>>j>>c)
        a[i][j]=c;
        r=1;
}
void tipar()
{
    int i,j;
    for(j=2;j<=n;j++)
        if(d[j]==1001)
            fout<<0<<" ";
        else
        fout<<d[j]<<" ";
        fout<<'\n';
    for(j=2;j<=n;j++)
        fout<<s[j]<<" ";
        fout<<'\n';
    for(j=2;j<=n;j++)
        fout<<t[j]<<" ";
        fout<<'\n';

}
void dijkstra(int r)
 { int min,poz;
    int i,j;
    s[r]=1;
    for(i=1;i<=n;i++)
    {
        d[i]=a[r][i];
        if(r!=i)
            t[i]=r;
    }
    for(i=1;i<=n;i++)
    {
        min=INF;
        for(j=1;j<=n;j++)
            if(s[j]==0)
                if(min>d[j])
                {
                min=d[j];
                poz=j;
                }
    s[poz]=1;
    for(j=1;j<=n;j++)
        if(s[j]==0)
            if(d[j]>d[poz]+a[poz][j])
            {
                d[j]=d[poz]+a[poz][j];
                t[j]=poz;
            }
    }
 }
   int main()
   {

    cit();
    dijkstra(1);
    tipar();
   }