#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <climits>
using namespace std;

const int NMAX = 50001;

int N, M;
vector< pair<int, int> > vecini[NMAX];
int D[NMAX];
bool inQueue[NMAX];

struct sortValue {
    bool operator()(int x, int y) {
        return D[x] > D[y];
    }
};

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

void Dijkstra(int root) {
    for(int i=1; i<=N; i++)
        D[i] = INT_MAX;

    D[root] = 0;
    inQueue[root] = true;
    q.push(root);

    int node;
    while(!q.empty()) {
        node = q.top();
        q.pop();
        inQueue[node] = false;

        for(unsigned int i=0; i<vecini[node].size(); i++) {
            int vecin = vecini[node][i].first;
            int dist = vecini[node][i].second;

            dist += D[node];
            if(dist < D[vecin]) {
                D[vecin] = dist;

                if(!inQueue[vecin]) {
                    q.push(vecin);
                    inQueue[vecin] = true;
                }
            }
        }
    }
}

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

    fin >> N >> M;

    int x, y, d;
    for(int i=0; i<M; i++) {
        fin >> x >> y >> d;
        vecini[x].push_back(make_pair(y, d));
    }

    Dijkstra(1);

    for(int i=2; i<=N; i++)
        if(D[i]!=INT_MAX)
            fout << D[i] << ' ';
        else fout << "0 ";

    fin.close();
    fout.close();
    return 0;
}