#include <cstring>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits>
using namespace std;

#define INFINIT 1000000

const int MAXN = 50005;

int N, M;
vector< pair<int, int> > G[MAXN];
int Dmin[MAXN];

void ReadData(string in) {
    ifstream fin(in.c_str());

    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b, c;

        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
}

void Solve() {
    bool InQueue[MAXN];
    queue<int> Q;

    memset(Dmin, INFINIT, sizeof(Dmin));
    memset(InQueue, false, sizeof(InQueue));

    Dmin[1] = 0;
    Q.push(1);
    InQueue[1] = true;

    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        InQueue[nod] = false;

        for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
            if (Dmin[nod] + it->second < Dmin[it->first]) {
                Dmin[it->first] = Dmin[nod] + it->second;
                if (!InQueue[it->first]) {
                    Q.push(it->first);
                    InQueue[it->first] = true;
                }
            }
    }
}

void WriteData(string out) {
    ofstream fout(out.c_str());

    for (int i = 2; i <= N; ++i)
        fout << (Dmin[i] < INFINIT ? Dmin[i] : 0) << " ";
}

int main() {
    ReadData("dijkstra.in");
    Solve();
    WriteData("dijkstra.out");
}