#include <iostream>
#include <fstream>
#define INFINIT 999999
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int main()
{
    int n, m, sursa=1, x, y;
    f>>n>>m;
    int G[n+1][n+1];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            G[i][j]=0;
    while(f>>x>>y)
        f>>G[x][y];

    // ----------- DIJKSTRA -------------

    // Initializarea drumului minim de la sursa la noduri
    int drum_min[n+1];
    for(int i=1; i<=n; i++)
        drum_min[i]=INFINIT;
    drum_min[sursa]=0;

    // COADA
    int coada[3*n], p, u;
    p=u=1;
    coada[u]=sursa;
    x=sursa;
    while(p<=u)
    {

        for(int j=1; j<=n; j++)
        {
            if(G[x][j])
            {
                cout<<x<<" "<<j<<endl;
                if(drum_min[x]+G[x][j] < drum_min[j])
                {
                    drum_min[j]=drum_min[x]+G[x][j];
                    coada[++u]=j;
                }
            }
        }
        p++;x=coada[p];
    }
    cout<<endl<<endl;
    // Afisarea drumurilor minime
    for(int i=2; i<=n; i++)
        g<<drum_min[i]<<' ';

    // ----------------------------------
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cout<<G[i][j]<<" \n"[j==n];
    return 0;
}