#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <fstream>

#define INF INT_MAX
using namespace std;

class Graph{
    private:
        int n, m;
        vector<pair<int, int> > *G;
        int *distance;
        int *father;
    public:
        Graph();
        ~Graph();

        void Dijkstra();

        friend istream& operator>>(istream&, Graph&);
        friend ostream& operator<<(ostream&, const Graph&);
};

Graph::Graph() {
    n = m = 0;
    G = nullptr;
    distance = nullptr;
    father = nullptr;
}

Graph::~Graph() {
    delete[] G;
    delete[] distance;
    delete[] father;
}

istream& operator>>(istream& in, Graph& obj) {
    in >> obj.n >> obj.m;
    obj.G = new vector<pair<int, int> >[obj.n + 1];
    obj.distance = new int[obj.n + 1];
    obj.father = new int[obj.n + 1];
    fill(obj.distance, obj.distance + obj.n + 1, 0);
    fill(obj.father, obj.father + obj.n + 1, 0);
    int x = 0, y = 0, z = 0;
    for (int i = 0 ; i < obj.m ; ++i) {
        in >> x >> y >> z;
        obj.G[x].push_back(make_pair(y, z));
    }
    return in;
}

void Graph::Dijkstra() {
    for(int i = 1 ; i <= n; ++i)
        distance[i] = INF;

    auto visited = new int[n + 1];
    fill(visited, visited + n + 1, 0);

    distance[1] = 0;
    priority_queue< pair<int, int> , vector<pair<int, int> > , greater<pair<int, int> > > Q;
    vector<int> S;
    Q.push(make_pair(distance[1], 1));
    while(!Q.empty()) {
        int u = Q.top().second;
        Q.pop();
        if(!visited[u]) {
            for (auto j : G[u]) {
                int Wuv = j.second;
                int v = j.first;
                if (distance[u] + Wuv < distance[v]) {
                    distance[v] = distance[u] + Wuv;
                    Q.push(make_pair(distance[v], v));
                    father[v] = u;
                }
            }
        }
        if(visited[u] == 0) {
            visited[u] = 1;
            S.push_back(u);
            if(S.size() == n) {
                break;
            }
        }
    }
}

ostream& operator<<(ostream& out, const Graph& obj) {
    for(int i = 2 ; i <= obj.n ; ++i){
        (obj.distance[i] == INF) ? out << 0 << ' ' : out << obj.distance[i] << ' ';
    }
    return out;
}

int main() {
    ifstream fin("dijkstra.in");
    Graph * G = new Graph();
    fin >> *G;
    G->Dijkstra();
    ofstream fout("dijkstra.out");
    fout << *G;
    return 0;
}