#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <array>

const int nmax = 100005, inf = INT_MAX;
int n, m;
std::array<std::vector<std::pair<int, int>>, nmax> graph;
std::array<int, nmax> dist;
std::set<std::pair<int, int>> S;

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

void read()
{
    fin >> n >> m;
    int x, y, c;
    for (int i = 0;i < m;i++)
    {
        fin >> x >> y >> c;
        graph[x].push_back({ y,c });

    }
    dist.fill(inf);
    dist[1] = 0;
}

void Dijsktra()
{
    S.insert({ 1,0 });

    while (!S.empty())
    {
        int node = S.begin()->first;
        int d = S.begin()->second;
        S.erase(S.begin());

        for (auto it : graph[node])
        {
            int next = (&it)->first;
            int cost = (&it)->second;
            if (dist[next] > dist[node] + cost)
            {
                if (dist[next] != inf)
                    S.erase(S.find({ next, dist[next] }));
                dist[next] = dist[node] + cost;
                S.insert({ next,dist[next] });
            }
        }
    }
}

void print()
{
    for (int i = 2;i <= n;i++)
    {
        fout << dist[i] << " ";
    }
}

int main()
{
    read();
    Dijsktra();
    print();

    return 0;
}