#include<iostream>
#include<fstream>
using namespace std;
int a[100][100],m,n;
int main()
{
    ifstream f("graf.in");
    int x,y,c,k,i,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==0&&i!=j)
                a[i][j]=1000000000;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            if(i!=k)
                for(j=1;j<=n;j++)
                    if(j!=k)
                        if(a[i][j]>a[i][k]+a[k][j])
                            a[i][j]=a[i][k]+a[k][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                if(a[i][j]==1000000000)
                    cout<<"nu exista drum intre "<<i<<" si "<<j<<"\n";
                else
                    cout<<"drumul minim intre "<<i<<" si "<<j<<" este "<<a[i][j]<<"\n";
    return 0;
}