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

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

constexpr int inf = std::numeric_limits<int>::max();

/**int a[50001][50001];**/
int * a[50001];
int numNodes, numArcs, dist[50001];
bool visited[50001] = { false };

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

    for(int i = 1; i <= numNodes; ++i) {
        a[i] = new int[numNodes + 1];
    }

    int nod1, nod2, cost;

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

        a[nod1][nod2] = cost;
    }
}

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

void Dijkstra()
{
    for(int t = 1; t <= numNodes; ++t) {
        if(a[1][t] > 0)
            dist[t] = a[1][t];
        else
            dist[t] = inf;
    }

    visited[1] = true;

    for(int i = 2; i <= numNodes; ++i) {
        for(int j = 1; j <= numNodes; ++j) {
            if(a[i][j] > 0 && dist[i] + a[i][j] < dist[j] && !visited[j]) {
                dist[j] = dist[i] + a[i][j];
            }
        }
        visited[i] = true;
    }
}

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

    return 0;
}