#include <iostream>

using namespace std;
#define inf 10000;
int a[1000][1000],n,m,pre[1000];

void citire()
{
    freopen("dijkstra.in","r",stdin);

    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=inf;

    for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d %d %d", &x,&y,&z);
            a[x][y]=z;
        }
}

void dijkstra()
{
    int d[1000] = {0},viz[1000]={0},poz=0;
    viz[1]=1;
    pre[1]=0;

    for(int i=2;i<=n;i++)
        {
            d[i]=a[1][i];
            pre[i]=1;
        }

    for(int i=1;i<=n-1;i++)
        {
            int dmin=inf;
            for(int j=1;j<=n;j++)
                    if(viz[j]==0 && dmin> a[1][j])
                        {
                            dmin=a[1][j];
                            poz=j;
                        }
            viz[poz]=1;
            cout<<dmin<<" ";
            cout<<poz<<endl;
            for(int j=1;j<=n;j++)
                {
                    if((!viz[j])&&(d[j]>dmin+a[poz][j]))
                        {
                            d[j]=a[poz][j]+dmin;
                            pre[j]=poz;
                        }
                }
        }
    for(int j=1;j<=n;j++)
            cout<<pre[j]<<" ";
    cout<<endl;
    for(int j=1;j<=n;j++)
        cout<<d[j]<<" ";

    /*freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=n;i++)
        printf("%d ", d[i]);*/
}


int main()
{
    citire();



    dijkstra();
    return 0;
}