#define submit
#ifdef submit
    #define fisier "dijkstra"
#else
    #define fisier "ULTRA"
#endif

#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");



const int
N = 50000,
M = 250000,
INF = (1 << 31) - 1;

int
n, m,
dist[N];

bool
vizitat[N];

#include <vector>
std::vector<std::pair<int, int>> vecini[N];



int idx_min_dist()
{
    int rt;
    for (rt = 0; rt < n; rt++)
        if (!vizitat[rt])
            break;

    for (int i = rt + 1; i < n; i++)
        if (!vizitat[i] && dist[i] < dist[rt])
            rt = i;

    return rt;
}



int main()
{
    in >> n >> m;

    *dist = 0;
    for (int i = 1; i < n; i++)
        dist[i] = INF;

    while (m--)
    {
        int a, b, c;
        in >> a >> b >> c; a--; b--;
        vecini[a].push_back({b, c});
    }

    for (int i = 0; i < n; i++)
    {
        int sursa = idx_min_dist();
        for (auto vec: vecini[sursa])
            dist[vec.first] = std::min(dist[vec.first], dist[sursa] + vec.second);
        vizitat[sursa] = true;
    }

    for (int i = 1; i < n; i++)
        out << dist[i] << ' ';
}