#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int N, M;
const int inf = 0x7fffffff;
vector<vector<int>> arcs;
vector<int> distances;

int main() {
    in >> N >> M; //citim nr noduri/arce
    arcs.resize(N+1, vector<int>(N+1, inf));
    distances.resize(N+1, inf); //initial consideram distantele spre toate nodurile iufinite
    
    for (int i = 1; i <= M; ++i) {
        int cost, a, b;
        in >> a >> b >> cost; //citim arcele
        arcs[a][b] = cost;
    }
    
    distances[1] = 0; //nodul de start
    
    queue<int> tobevisited; //ce noduri sa vizitam
    tobevisited.push(1); //incepem de la nodul de start
    
    while(!tobevisited.empty()){//cat timp avem ce vizita
        int nod = tobevisited.front();
        tobevisited.pop();
        for(int i = 1; i <= N; ++i) {//verificam toate nodurile in care putem ajunge din nod
            if(arcs[nod][i] == inf) continue;
            if(distances[i] > distances[nod] + arcs[nod][i]) {//daca putem ajunge intr-un nod i, si ajugnem mai rapid decat stiam pana acum
                distances[i] = distances[nod] + arcs[nod][i];//actualizam distanta
                tobevisited.push(i);//si revizitam nodul sa verificam daca se scurteaza si alte distante
            }
        }
    }
    
    for (int i = 2; i <= N; ++i) {
        if (distances[i] == inf) {
            distances[i] = 0;
        }
        out << distances[i] << ' ';
    }
    out << '\n';
    
    in.close();
    out.close();
}