#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <utility>
#include <bitset>
#include <climits>

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

    int vertexNr, edgesNr;
    int *distances;
    std::bitset<50010> processedVertex;
    std::priority_queue<std::pair<int, int>> unprocessedVertex;
    std::vector<std::pair <int, int>> edges[50010];

    fin >> vertexNr >> edgesNr;
    distances = new int[vertexNr+1];
    distances[1] = 0;
    for (int i = 2; i <= vertexNr; i++)
    {
        distances[i] = INT_MAX;
    }
    for (int i = 0; i < edgesNr; i++)
    {
        int start, end, cost;
        fin >> start >> end >> cost;
        edges[start].push_back({end, cost});
    }

    unprocessedVertex.push({1,0});
    while (!unprocessedVertex.empty())
    {
        int currentVertex = unprocessedVertex.top().first;
        int currDistance = unprocessedVertex.top().second;
        unprocessedVertex.pop();
        if (processedVertex[currentVertex])
            continue;
        for (auto it = edges[currentVertex].begin(); it != edges[currentVertex].end(); it++)
        {
            int toVertex = it->first;
            int cost = it->second;
            if (distances[toVertex] > currDistance + cost)
            {
                distances[toVertex] = currDistance + cost;
                unprocessedVertex.push({toVertex, distances[toVertex]});
            }
        }
        processedVertex[currentVertex] = 1;
    }

    for (int i = 2; i <= vertexNr; i++)
    {
        fout << distances[i] << " ";
    }
    fout << std::endl;
}