#include <iostream>
#include <fstream>
#include <utility>
#include <list>
#include <set>
#include <vector>
#include <iterator>

using namespace std;

#define INF 0x3f3f3f3f

class Graph2 {
    public:
        Graph2() {};
        void readGraph(int start);
        void dijkstra(int start);
};

void Graph2 :: readGraph(int start) {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    list<pair<int, int>> *adjList;
    int n, m;

    fin >> n >> m;

    adjList = new list<pair<int, int>> [n];

    for (int i = 0; i < m; i++) {
        int a, b, w;
        fin >> a >> b >> w;
        adjList[a].push_back(make_pair(b, w));
    }

    set<pair<int, int>> setProc;

    vector<int> dist(n, INF);

    dist[start] = 0;
    setProc.insert(make_pair(0, start));

    while (!setProc.empty()) {
        pair<int, int> tmp = *(setProc.begin());
        setProc.erase(setProc.begin());

        int u = tmp.second;

        list<pair<int, int>> :: iterator i;
        for (i = adjList[u].begin(); i != adjList[u].end(); i++) {
            int v = (*i).first;
            int w = (*i).second;

            if (dist[v] > dist[u] + w) {
                if (dist[v] != INF)
                    setProc.erase(setProc.find(make_pair(dist[v], v)));

                dist[v] = dist[u] + w;
                setProc.insert(make_pair(dist[v], v));
            }
        }
    }

    for (int i = 2; i <= n; i++)
        fout << dist[i] << " ";
}
/*
void Graph2 :: dijkstra(int start) {
    ofstream fout("dijkstra.out");

    set<pair<int, int>> setProc;

    vector<int> dist(n, INF);

    dist[start] = 0;
    setProc.insert(make_pair(0, start));

    while (!setProc.empty()) {
        pair<int, int> tmp = *(setProc.begin());
        setProc.erase(setProc.begin());

        int u = tmp.second;

        list<pair<int, int>> :: iterator i;
        for (i = adjList[u].begin(); i != adjList[u].end(); i++) {
            int v = (*i).first;
            int w = (*i).second;

            if (dist[v] > dist[u] + w) {
                if (dist[v] != INF)
                    setProc.erase(setProc.find(make_pair(dist[v], v)));

                dist[v] = dist[u] + w;
                setProc.insert(make_pair(dist[v], v));
            }
        }
    }

    for (int i = 1; i <= n; i++)
        fout << dist[i] << " ";

    fout.close();
}
*/
int main()
{
    Graph2 X;
    X.readGraph(1);
    return 0;
}