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

using namespace std;

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

vector<pair<int, int> > v[50002];

bool inQ[50002];

int d[500002];

const int INF = 30000;

int n, m, a, b, c;

struct compD {

    bool operator() (int x, int y) {

        return d[x] > d[y];

    }

};

priority_queue<int, vector<int>, compD> q;

void dijkstra(int start) {

    for (int i=1; i<=n; i++) {
        d[i] = INF;
    }

    d[start] = 0;

    q.push(start);
    inQ[start] = 1;

    while (!q.empty()) {

        int poz = q.top();
        q.pop();

        for (int i=0; i<v[poz].size(); i++) {

            int vecin = v[poz][i].first;
            int cost = v[poz][i].second;

            if (d[vecin] > d[poz] + cost) {
                d[vecin] = d[poz] + cost;

                if (!inQ[vecin]) {
                    q.push(vecin);
                    inQ[vecin] = 1;
                }

            }

        }

    }

}

int main()
{

    fin>>n>>m;

    for (int i=1; i<=m; i++) {

        fin>>a>>b>>c;

        v[a].push_back(make_pair(b, c));

    }

    dijkstra(1);

    for (int i=2; i<=n; i++) {
        fout<<d[i]<<" ";
    }

    return 0;
}