#include <fstream>
#include <vector>
#include <memory.h>
#include <queue>

#define inf 0x3f3f3f3f

#define MAXN 50005

using namespace std;

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

int cost[MAXN], N, M;

struct str{
    int node, c;

    bool operator < (const str& other) const {
        return c > other.c;
    }
};

vector <str> graph[MAXN];
priority_queue <str> Q;

inline void Read() {
    int x, y, z;

    fin >> N >> M;

    for (int i = 1; i <= M; i++) {
        fin >> x >> y >> z;

        graph[x].push_back({y, z});
    }
}

inline void Dijkstra(int nod) {
    int z, cc;

    memset(cost, inf, sizeof(cost));
    Q.push({nod, 0});
    cost[nod] = 0;

    while (!Q.empty()) {
        z = Q.top().node;
        cc = Q.top().c;

        Q.pop();

        if (cost[z] != cc)
            continue;

        for (auto x : graph[z]) {
            if (cost[x.node] > cost[z] + x.c) {
                cost[x.node] = cost[z] + x.c;
                Q.push({x.node, cost[x.node]});
            }
        }
    }
}

int main () {
    Read();
    Dijkstra(1);

    for (int i = 2; i <= N; i++) {
        if (cost[i] == inf)
            cost[i] = 0;
        fout << cost[i] << " ";
    }

    fin.close(); fout.close(); return 0;
}