#include<iostream>
#include<fstream>
using namespace std;
float c[100][100],infinite=10000;
int n,m,d[100][100];
void citire()
{
    int i,x,y,j;
    float cost;
    ifstream f("roy_floyd.in");
f>>n>>m;
for(i=1;i<=m;i++)
{
    f>>x>>y>>cost;
    c[x][y]=cost;
} for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
    if(i!=j&&c[i][j]==0)
    c[i][j]=infinite;
}
void drumul_initial()
{
    int i,j;
    for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
    if(i!=j&&c[i][j]!=infinite)
        d[i][j]=i;
    if(i!=j&&c[i][j]==infinite)
        d[i][j]=infinite;
}}
void drum(int i,int j)
{
    if(i==j)
        cout<<i<<" ";
    else {drum(i,d[i][j]);
    cout<<j<<" ";}

}
void afisare()
{
    int i,j;
    for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
    if(i!=j)
    if(c[i][j]!=infinite)
{
    cout<<"costul drumului de la "<<i<<" la "<<j<<" = "<<c[i][j];
    cout<<" drumul este: ";drum(i,j);
    cout<<endl;
}
}
void Floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
    if(c[i][j]>c[i][k]+c[k][j])
{
    c[i][j]=c[i][k]+c[k][j];
    d[i][j]=d[k][j];
}
}
int main()
{
    citire();
    drumul_initial();
    Floyd();
    afisare();

}