#include <bits/stdc++.h>
using namespace std;
float c[100][100],infinite=10000;
int n,m,dr[100][100];
int sume[101];
ifstream f("2.in");
int x,y,d;
void citire()
{
    int i,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>d;
        c[x][y]=d;
    }
        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)
        dr[i][j]=i;
    if(i!=j&&c[i][j]==infinite)
        dr[i][j]=infinite;
}}

void drum(int i,int j)
{
    if(i==j)
        cout<<i<<" ";
    else {drum(i,dr[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];
    dr[i][j]=dr[k][j];
}
}
int main()
{
    citire();
    drumul_initial();
    Floyd();
    int minim=10000;
    int i,j;
   int k=0;
    for(i=1;i<=n;i++)
    {int sumatotala=0;
        for(j=1;j<=n;j++)
            sumatotala+=dr[i][j];
cout<<sumatotala<<" ";
            if(sumatotala<minim){sume[++k]=sumatotala;minim=sumatotala;}
    }
    int poz;
for(i=1;i<=k;i++)
{
    if(sume[i]==minim)poz=i;
}
cout<<"Nodul sursa este "<<i;



}