#include<iostream>
#include<fstream>
using namespace std;
fstream f("dijkstra.in",ios::in),g("dijkstra.out",ios::out);
unsigned int i,j,k,c;
unsigned long n,m,a[100][100];
void citire()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(i==j)
            a[i][j]=0;
        else
    while(m!=0)
    {f>>i>>j>>c;
    a[i][j]=c;
    m--;
    }


}
int main()
{  citire();

for(k=1;k<=n;k++)
    for(j=1,i=1;j<=n;j++)
           if(a[i][k]&&a[k][j]&&(a[i][j]>a[i][k]+a[k][j]||!a[i][j])&&i!=j)
               a[i][j]=a[i][k]+a[k][j];

    for(j=1;j<=n;j++)
    if(a[i][j]!=0)
    g<<a[i][j]<<" ";
    return 0;
}