#include <iostream>
#include <vector>
#include <queue>
#include <utility> // pair
#include <climits> // INT_MAX
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
struct Graph {
    int V;
    vector<vector<pair<int,int> > > adj;
    vector<int> dist;

    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
        dist.resize(V, INT_MAX);
    }

    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // undirected
    }

    void dijkstra(int start) {
        // Min-heap: pair(distance, node)
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            int u_dist = pq.top().first;
            int u = pq.top().second;
            pq.pop();

            // Skip if we already found a shorter path
            if (u_dist > dist[u]) continue;

           for (size_t i = 0; i < adj[u].size(); i++) {
    pair<int,int> edge = adj[u][i];
    int v = edge.first;
    int w = edge.second;

    if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push(make_pair(dist[v], v));
    }
}
        }
    }
};

int main() {
    int n, m;
    f >> n >> m;

    Graph g(n);

    for (int i = 1; i <=m; i++) {
        int x, y, z;
        f>> x >> y >> z;
        x--; y--; // if input is 1-indexed
        g.addEdge(x, y, z);
    }

    int start;
  //  cin >> start;
    start--; // if input is 1-indexed

    g.dijkstra(1);

    for (int i = 1; i <=n; i++) {
        h<< g.dist[i] << " ";
    }


    return 0;
}