#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
    int n,m;
    int a[502][501];
    int i,j,x,y,z,k;
    f>>n>>m;
    for (i=1;i<=m;i++)
        for(j=1;j<=3;j++)
            {f>>x>>y>>z;
            a[x][y]=z;}
    for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                if(i!=j&&a[i][k]&&a[k][j]&&(a[i][j]==0||a[i][j]>a[i][k]+a[k][j])) a[i][j]=a[i][k]+a[k][j];
    for (i=2;i<=n;i++)
        cout<<a[1][i]<<" ";
}