#include <fstream>
#include <vector>
#include <cstring>
#include <set>

#define pair pair<int, int>

using namespace std;


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

const int inf = 0x3f3f3f3f;
const int NM = 50005;

vector <pair> G[NM];
multiset <pair> H;
pair crt;

int N, E, edge, from, to, cost, i, node;
bool visited[NM];
int D[NM];

int main()
{
    in >> N >> E;
    for (edge = 1; edge <= E; ++edge) {
        in >> from >> to >> cost;
        G[from].push_back({to, cost});
    }

    memset(D, inf, sizeof D);
    D[1] = 0; H.insert({1, 0});   // node, cost

    while (!H.empty()) {
        crt = *(H.begin());
        node = crt.first;
        cost = crt.second;
        H.erase(H.begin());

        visited[node] = 1;

        for (auto &it: G[node]) {
            if (!visited[it.first] && it.second + cost < D[it.first]) {
                if (D[it.first] != inf) {
                    H.erase(H.find({it.first, D[it.first]}));
                }
                D[it.first] = it.second + cost;
                H.insert({it.first, D[it.first]});
            }
        }
    }

    for (i = 2; i <= N; ++i) {
        if (D[i] == inf)
            out << "0 ";
        else
            out << D[i] << ' ';
    }


    return 0;
}