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

#define INF             (2147483647 - 20000)
#define MAX_NODES       50001

using namespace std;

int sol[MAX_NODES];

struct comp {
    bool operator() (int x, int y) {return sol[x] > sol[y] ? true : false;}
};

vector<pair<int, int> > graf[MAX_NODES];
priority_queue<int, vector<int>, comp> q;
int n, m, x, y, w;

void dijkstra()
{
    int node;
    q.push(1);
    for (int i = 2; i <= n; i++) {
        sol[i] = INF;
    }

    while (!q.empty()) {
        node = q.top();
        q.pop();

        cout << node << ' ';
        for (const auto& it : graf[node]) {
            if (sol[node] + it.second < sol[it.first]) {
                sol[it.first] = sol[node] + it.second;
                q.push(it.first);
            }
        }
    }

    cout << endl;
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> w;
        graf[x].push_back(make_pair(y, w));
    }

    dijkstra();

    for (int i = 2; i <= n; i++) {
        if (sol[i] == INF)
            out << 0 << ' ';
        else
            out << sol[i] << ' ';
    }

    return 0;
}