#include <bits/stdc++.h>

using namespace std;
#define MAX_NODES 5002


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

int adj[MAX_NODES][MAX_NODES];
vector <int> parent(MAX_NODES, 0);
vector <long long> dist(MAX_NODES, LLONG_MAX);
    int nodes, edges;
    int x, y, z;



void dijkstra(int node) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Queue;

    dist[node] = 0; // Distance to the source node is 0
    parent[node] = 0; // Parent of the source node is 0

    Queue.push(make_pair(node, dist[node])); // Push the source node and its distance into the priority queue

    while (!Queue.empty()) {
        int curNode = Queue.top().first;
        int curDist = Queue.top().second;
        Queue.pop();

        // Iterate over all neighbors of the current node
        for (int neigh = 1; neigh <= nodes; neigh++) {
            // If there is an edge from curNode to neigh and relaxing the edge results in a shorter path
            if (adj[curNode][neigh] != 0 && curDist + adj[curNode][neigh] < dist[neigh]) {
                dist[neigh] = curDist + adj[curNode][neigh]; // Update the distance to neigh
                parent[neigh] = curNode; // Update the parent of neigh
                Queue.push(make_pair(neigh, dist[neigh])); // Push neigh and its updated distance into the priority queue
            }
        }
    }
}

int main() {



    fin>>nodes>>edges;

    for (int i = 0; i < edges; i++) {
        fin>>x>>y>>z;
        adj[x][y] = z;
    }

    dijkstra(1);

    for (int i = 2; i<=nodes; i++) {
        fout<<dist[i]<<' ';
    }


    return 0;
}