#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<pair<int,int>> arcs[50001];
int distances[50001];

int main() {
    in >> N >> M; //citim nr noduri/arce
    fill(distances, distances+50001, 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].emplace_back(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(auto& vecin : arcs[nod]) {//verificam toate nodurile in care putem ajunge din nod
            int destinatie = vecin.first, cost = vecin.second;
            if(distances[destinatie] > distances[nod] + cost) {//daca putem ajunge intr-un nod i, si ajugnem mai rapid decat stiam pana acum
                distances[destinatie] = distances[nod] + cost;//actualizam distanta
                tobevisited.push(destinatie);//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();
}