#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 50005;
const int INF = 0x3f3f3f3f;

struct Heap {
    int node, cost;
    Heap(int node, int cost) : node(node), cost(cost) {}
    //nu mai incurca semnele. gandeste logic
    bool operator < (const Heap &other) const {
        cost > other.cost;
    }
};

int n, m;
int dist[N_MAX];
vector <pair <int, int> > graph[N_MAX];
priority_queue <Heap> q;

void read() {
    ifstream fin("dijkstra.in");

    fin >> n >> m;

    int x, y, z;
    while (m--) {
        fin >> x >> y >> z;
        graph[x].emplace_back(y, z);
    }

    fin.close();
}

void solve() {
    int node, cost, new_dist;

    //nu mai uita functia asta!
    memset(dist, INF, sizeof dist);
    dist[1] = 0;

    q.emplace(1, 0);

    while (!q.empty()) {
        node = q.top().node;
        cost = q.top().cost;
        q.pop();

        if (cost != dist[node]) {
            continue;
        }

        for (auto &son : graph[node]) {
            new_dist = cost + son.second;
            if (new_dist < dist[son.first]) {
                dist[son.first] = new_dist;
                q.emplace(son.first, new_dist);
            }
        }
    }
}

void write() {
    ofstream fout("dijkstra.out");

    for (int i = 2; i <= n; ++i) {
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
    }

    fout.close();
}

int main() {
    read();
    solve();
    write();

    return 0;
}