#include <iostream>
#include <fstream>

using namespace std;

const int inf=10000;
int n,m;
int urm[50][50];
int cost[50][50];
int d[50][50];
void init()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            d[i][j]=cost[i][j];
            if(cost[i][j]>0 && cost[i][j]<inf)
                urm[i][j]=j;
        }
}

void citire()
{
    ifstream fin("graf.txt");
    fin>>n>>m;
    int ii,jj,c;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if (i==j) cost[i][j]=0;
            else cost[i][j]=inf;

    for(int i=1; i<=m; i++)
    {
        fin>>ii>>jj>>c;
        cost[ii][jj]=cost[jj][ii]=c;
    }
    fin.close();
}

void roy()
{
    for(int k=1; k<=n; k++)
        for(int x=1; x<=n; x++)
            for(int y=1; y<=n; y++)
                if(d[x][y]>d[x][k]+d[k][y])
                {
                    d[x][y]=d[x][k]+d[k][y];
                    urm[x][y]=urm[x][k];
                }
}
void drum(int x, int y)
{
    cout<<x<<" ";
    if(x!=y)
        drum(urm[x][y],y);
}
int main()
{
    citire();
    init();
    roy();
    for(int x=1; x<n; x++)
        for(int y=x+1; y<=n; y++)
            if(d[x][y]==inf)
                cout<<"nu exista drum de la "<<x<<" la "<<y<<endl;
            else
            {
                cout<<"cost dr minim de la "<<x<<" la "<<y<<" este "<<d[x][y]<<" pe traseul ";
                drum(x,y);
                cout<<endl;
            }

    return 0;
}