#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define N  50001
#define M 250001
#define INF 0x3f3f3f3f
#define node first
#define cost second
#define iter vector<pair<int, int> >::iterator

using namespace std;

int D[N];

struct Comp {
    bool operator()(int a, int b) {
        return D[a] > D[b];
    }
};

vector<pair<int, int> > L[N];
priority_queue<int, vector<int>, Comp> Q;
bitset<N> E;

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        L[a].push_back(make_pair(b, c));
    }

    for (int i = 2; i <= n; ++i)
        D[i] = INF;
    
    for (Q.push(1); !Q.empty(); Q.pop()) {
        int node = Q.top();
        E[node] = 0;
        for (iter it = L[node].begin(); it != L[node].end(); ++it) {
            int val = D[node] + it -> cost;
            if (val < D[it -> node]) {
                D[it -> node] = val;
                if (!E[it -> node]) {
                    Q.push(it -> node);
                    E[it -> node] = 1;
                }
            }
        }
    }

    for (int i = 2; i <= n; ++i)
        fout << (D[i] < INF ? D[i] : 0) << " ";
    fout << "\n";

    return 0;
}