#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <iomanip>
#include <utility>
#include <string>
#include <queue>

const std::string InputFile = "dijkstra.in";
const std::string OutputFile = "dijkstra.out";
const int INF = 0x7fffffff;

class Edge {
public:
    int destination, cost;
    Edge(int dest, int cost) : destination(dest), cost(cost) {
    }
    Edge() : destination(-1) , cost(-1) {
    }
};

auto comparator = [](const Edge& a, const Edge& b) { return a.cost > b.cost; };
typedef std::vector<std::vector<Edge> > Graph;
typedef std::priority_queue<Edge, std::vector<Edge>, decltype(comparator)> myHeap;

std::istream& operator >> (std::istream& stream, Graph& graph) {
    int N, M;
    stream >> N >> M;
    graph.resize(N+1);
    for (register int i = 0; i < M; i++) {
        int source, destination, cost;
        stream >> source >> destination >> cost;
        graph[source].push_back(Edge(destination,cost));
    }
    return stream;
}

std::ostream& operator << (std::ostream& stream, std::vector<int>& v) {
    for (auto it = v.begin()+2; it < v.end(); ++it)
        stream << ((*it) == INF ? -1 : (*it)) << ' ';
    return stream;
}

std::vector<int> dijkstra(Graph& graph, int source) {
    std::vector<int> distances(graph.size(), INF);
    myHeap pq(comparator);

    distances[source] = 0;
    pq.push(Edge(source,0));

    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        int node = e.destination;
        for (auto it = graph[node].begin(); it < graph[node].end(); ++it) 
            if (distances[it->destination] > distances[node] + it->cost) {
                distances[it->destination] = distances[node] + it->cost;
                pq.push(Edge(it->destination, distances[it->destination]));
            }
    }
    return distances;
}

int main(void) {
    std::ifstream fin(InputFile);
    std::ofstream fout(OutputFile);
    Graph graph;
    std::vector<int> distances;

    fin >> graph;
    distances = dijkstra(graph, 1);
    fout << distances << '\n';

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