#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
# define INF 0x3f3f3f3f
using namespace std;
typedef pair<int, int> edge;
vector<int> Dijkstra(const vector< vector<edge> >& graph, int src)
{
    priority_queue< edge, vector <edge> , greater<edge> > pq;
    vector<int> dist(graph.size(), INF);
    pq.push(make_pair(src, 0));
    dist[src] = 0;

    while (!pq.empty())
    {
        int u = pq.top().first;
        pq.pop();
        for (int i = 0; i < graph[u].size(); ++i)
        {
            int v = graph[u][i].first;
            int weight = graph[u][i].second;
            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(v, dist[v]));
            }
        }
    }
    return dist;
}
void print(FILE *out, vector<vector<int> > &dist) {
    int no_nodes = dist.size();
    for (int i = 0; i < no_nodes; ++i) {
        for (int j = 0; j < no_nodes; ++j) {
            if(dist[i][j] == INF) {
                fprintf(out, "inf ");
            } else {
                fprintf(out, "%d ", dist[i][j]);
            }
        }
        fprintf(out, "\n");
    }
}

int main()
{
    FILE *in = fopen("dijkstra.in", "r");
    FILE *out = fopen("dijkstra.out", "w");
    int n, m;
    fscanf(in, "%d %d", &n, &m);
    vector<vector<edge> >graph(n);

    for (int i = 0; i < m; i++) {
        int src;
        edge dest;
        fscanf(in, "%d %d %d", &src, &dest.first, &dest.second);
        dest.first--;
        graph[src - 1].push_back(dest);
    }

    vector<vector <int> > dist;
    vector <int> result = Dijkstra(graph, 0);
    for (int i = 1; i < result.size(); ++i) {
        fprintf(out, "%d ", result[i] == INF ? 0 : result[i]);
    }
    //dist.push_back(Dijkstra(graph, 0));
    //print(out, dist);

    fclose(in);
    fclose(out);
    return 0;
}