#include <fstream>
#include <vector>

using namespace std;

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

const int INF = INT_MAX;

// Reprezentăm lista de adiacență ca un vector de vectori
vector<pair<int, int>> listaAdiacenta[50005];  // listaAdiacenta[i] conține perechi (nod, cost) pentru nodul i

int dist[50005];
int fin[50005];

int main()
{
    for(int i = 1; i <= 50005; i++) {
        dist[i] = INF;
    }

    int n, S, m;
    in >> n >> m;

    S = 1; /// fac dijkstra pt nod 1

    int i, j, c;
    for(int z = 1; z <= m; z++){
        in >> i >> j >> c;
        // Adauga arc de la nodul i la nodul j cu costul c
        listaAdiacenta[i].emplace_back(j, c);
    }

    dist[S] = 0;  // Distanta de la sursa la sursa este 0

    for (int k = 1; k < n; k++) { /// am n - 1 noduri de verificat
        // Gasește nodul cu distanța minimă care nu a fost procesat
        int minim = INF;
        int nodMinim;

        for (int i = 1; i <= n; i++) {
            if (!fin[i] && dist[i] < minim) {
                minim = dist[i];
                nodMinim = i;
            }
        }

        if(minim != INF){
            fin[nodMinim] = 1;  // Marcheaza nodul ca finalizat

            for (auto &arc : listaAdiacenta[nodMinim]) {
                int vecin = arc.first;   // Nodul vecin
                int cost = arc.second;   // Costul arcului

                // Daca distanta pana la vecin este mai mare decat distanta pana la nodMinim plus costul arc
                if ((long long) dist[nodMinim] + cost < dist[vecin]) {
                    dist[vecin] = dist[nodMinim] + cost;
                }
            }
        }

    }

    for (int i = 2; i <= n; i++) {
        if (dist[i] != INF) out << dist[i] << " ";
        else out << "0 ";
    }

    return 0;
}