#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("graf.txt");
//ofstream fout("roy-floyd.out");
int a[105][105],n,m,x,y,c;
const int pinf=10000;
int citire()
{
    int i,j;
    fin>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i==j)
                a[i][j]=0;
            else
                a[i][j]=pinf;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        a[x][y]=c;
    }

}
void mat_dr()
{
    int i,j,k;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(a[i][j]>a[i][k] + a[k][j])
                    a[i][j]=a[i][k]+a[k][j];
}
int main()
{
    citire();
    int i,j;

    mat_dr();
     for(i=1; i<n; i++)
    {
            if(a[i][i+1]!=pinf)
                cout<<"Drumul minim dintre "<<i<<" și "<<i+1<<" este "<<a[i][i+1]<<" ";
            else
            cout<<"Nu exista"<<" ";
        cout<<endl;
    }
    return 0;
}