#include <iostream>
#include <fstream>
#include <queue>
#include <limits>
#include <vector>
#include <array>

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");

constexpr int INF = std::numeric_limits<int>::max();
constexpr int MAX = 50001;

std::vector<std::pair<int, int>> graph[MAX];

std::array<int, MAX> dist;

bool isInQueue[MAX] = { false };

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

std::priority_queue<int, std::vector<int>, comp> nodes;

int numNodes, numArcs;
constexpr int sursa = 1;

void Init()
{
    for(int i = 1; i <= numNodes; ++i) {
        dist[i] = INF;
    }

    dist[sursa] = 0;
}

void Read()
{
    f >> numNodes >> numArcs;

    int nod1, nod2, cost;

    Init();

    for(int i = 1; i <= numArcs; ++i) {
        f >> nod1 >> nod2 >> cost;

        graph[nod1].emplace_back(nod2, cost);
    }
}

void Dijkstra()
{
    nodes.push(sursa);
    isInQueue[sursa] = true;

    while(!nodes.empty()) {
        int currentNode = nodes.top();
        for(const auto& vecin : graph[currentNode]) {
            if(dist[currentNode] + vecin.second < dist[vecin.first]) {
                dist[vecin.first] = dist[currentNode] + vecin.second;
                if(!isInQueue[vecin.first]) {
                    nodes.push(vecin.first);
                    isInQueue[vecin.first] = true;
                }
            }
        }
        isInQueue[currentNode] = false;
        nodes.pop();
    }
}

void Print()
{
    for(int i = 2; i <= numNodes; ++i) {
        g << ((dist[i] == INF) ? 0 : dist[i]) << ' ';
    }
}

int main()
{
    Read();
    Dijkstra();
    Print();

    return 0;
}