#include <bits/stdc++.h>
using namespace std;

#define NMAX 50007
#define INF (1 << 30)
#define NO_PARENT -1

class Task {
public:
    void solve() {
        read_input();
        get_result();
        print_soultion();
    }

private:
    // numar de noduri
    int n;

    // numar de muchii
    int m;

    // vector de distante
    vector<int> dist;

    // vector de partinti folosit la reconstruirea path-ului
    vector<int> p;

    // liste de adiacenta
    vector<pair<int, int>> adj[NMAX];

    // sursa
    int source;

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

        fin >> n >> m;

        dist.resize(n + 1);
        p.resize(n + 1);

        for (int i = 1; i <= m; ++i) {
            int x, y, cost;

            fin >> x >> y >> cost;

            adj[x].push_back({y, cost});

            // decomentezi daca vrei ca graful sa fie neorientat
            // adj[y].push_back({x, cost});
        }

        fin.close();
    }

    void get_result() {
        source = 1;
        Dijkstra(source, dist, p);
    }

    void Dijkstra(int source, vector<int> &dist, vector<int> &p) {
        /*
            Min-heap ce va fi folosit pentru a stoca perechide tipul <distanta pana la sursa a nodului x, nodul x>.
            Este folosit pentru a extrage la fiecare pas nodul care are distanta cea mai mica pana la sursa.
        */
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        for (int i = 1; i <= n; ++i) {
            dist[i] = INF;
            p[i] = NO_PARENT;
        }

        dist[source] = 0;
        p[source] = 0;

        pq.push({dist[source], source});

        while (!pq.empty()) {
            pair<int, int> entry = pq.top();
            pq.pop();

            int node = entry.second;
            int cost = entry.first;

            // daca nodul are de fapt distanta mai mica
            if (cost > dist[node]) {
                continue;
            }

            for (auto &it : adj[node]) {
                int neighbour = it.first;
                int edge_cost = it.second;

                // aici de face relaxare de muchie
                if (dist[node] + edge_cost < dist[neighbour]) {
                    // update al distantei minime
                    dist[neighbour] = dist[node] + edge_cost;

                    // update al parintelui
                    p[neighbour] = node;
                    
                    // introduce in min-heap noua intrare 
                    pq.push({dist[neighbour], neighbour});
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (dist[i] == INF) {
                dist[i] = 0;
            }
        }
    }


    void print_soultion() {
        ofstream fout("dijkstra.out");
        
        for (int i = 1; i <= n; ++i) {
            if (i == source) {
                continue;
            }

            fout << dist[i] << " ";
        }

        fout.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}