//Infoarena. Arhiva Educationala. Floyd-Warshall/Roy-Floyd.
#include<iostream>
#include<fstream>
using namespace std;

void roy_floyd(int);

int N,M,P[10003][10003];

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);


    cin>>N>>M;

    int x,y,aux;
    for(int i=1;i<=M;i++){
        cin>>x>>y>>aux;
        P[x][y]=aux;
    }

    roy_floyd(N);  //Generam Matricea Distantelor Minime
    for(int i=2;i<=N;i++) cout<<P[1][i]<<" ";
}

void roy_floyd(int N){
    int dist;
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++){
                if(i==j) continue;
                else if(P[i][k]&&P[k][j]){
                    dist=P[i][k]+P[k][j];
                    if(P[i][j]==0 || P[i][j]>dist) P[i][j]=dist;
                }
            }
}