#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <bitset>
using namespace std;

#define INF 99999999
#define NMAX 50100

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

vector<pair<int, int> > graph[NMAX];
set<pair<int, int> > s; // pair<cost, nod>
int distances[NMAX];
int nodes;


inline void printSolution() {
    for(int i = 1; i < nodes; i++) {
        if (distances[i] == INF)
            out << 0 << " ";
        else
            out << distances[i] << " ";
    }
}

inline void initDistances() {
    distances[0] = 0;

    for (int i = 1; i < nodes; i++) {
        distances[i] = INF;
    }
}

int main() {

    int edges , edge1, edge2, cost;

    in >> nodes >> edges;

    for (int i = 0; i < edges; i++) {
        in >> edge1 >> edge2 >> cost;

        graph[edge1 - 1].push_back(pair<int, int>(cost, edge2 - 1));
    }

    in.close();

    int node;
    vector<pair<int, int> >::iterator it;

    initDistances();
    s.insert(make_pair(0, 0));
    bitset<NMAX> inSet(false);

    while (s.size() > 0) {
        node = (*s.begin()).second;
        cost = (*s.begin()).first;

        s.erase(*s.begin());

        for (it = graph[node].begin(); it != graph[node].end(); it++) {
            pair<int, int> neighbour = *it;

            if (neighbour.first + cost < distances[neighbour.second]) {
                distances[neighbour.second] = neighbour.first + cost;
                if (!inSet[neighbour.second]) {
                    s.insert(make_pair(distances[neighbour.second], neighbour.second));
                    inSet[neighbour.second] = true;
                }
            }
        }
    }

    printSolution();

    return 0;
}