#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijktra.in");
ofstream fout("diktra.out");

const int limit = 2147483647;
int graph[1000][1000],n,m,x,y,cost,D[1000],T[1000],visited[1000];
priority_queue <int> D_roads;

void Read(){
    fin >> n >> m;
    for(int i =1; i <= m; i++){
        fin >> x >> y >> cost;
        graph[x][y] = cost;
    }
}

bool AreAllVisited(){
    for(int i = 1; i <= n; i++)
        if(!visited[i])
            return false;
    return true;
}

int GetMostNearNode(){
    int minimum = limit,result = 1;
    for(int node = 1; node <= n; node++){
        if(D[node] < minimum && !visited[node]){//daca D[node] < minimum si nu e vizitat
            minimum = D[node];
            result = node;
        }
    }
    return result;
}

void Dijktra(int source){
    for(int i = 1; i <= n; i++) D[i] = limit;
    D[source] = 0;
    unsigned int current_node = source;

    while(!AreAllVisited()){
        //mergem la vecini
        visited[current_node] = 1;
        for(int i = 1; i <= n; i++){
            int cost_arc = graph[current_node][i];

            if(cost_arc && (D[current_node] + cost_arc < D[i]) && !visited[i]){
                D[i] = D[current_node] + cost_arc;
                T[i] = current_node;//am ajuns in i din current_node
            }
        }
        //il cautam pe nodul nevizitat x cu cea mai mica valoare D[x]
        current_node = GetMostNearNode();
        /*
        for(int i = 1; i <= n; i++){
            cout << visited[i] << " ";
        }
        cout << "\n";
        */
    }

    for(int i =2; i <= n; i++){
        fout << D[i] << " ";
    }
}



int main()
{
    Read();
    Dijktra(1);
    return 0;
}