#include <fstream>
#include <vector>
const std::string programName = "dijkstra";
std::ifstream f(programName + ".in");
std::ofstream g(programName + ".out");
const int MAX = 5e4, INF = 0x3f3f3f3f;
void read(int&, int&, std::vector < std::pair <int, int> > []);
void print(int, int[]);
void Dijkstra(int, int, int[], std::vector < std::pair <int, int> > []);
int main() {
    int N, M;
    int Dist[MAX + 5] = {0};
    std::vector < std::pair <int, int> > Graph[MAX + 5];
    read(N, M, Graph);
    Dijkstra(1, N, Dist, Graph);
    print(N, Dist);
    return 0x0;
}
void read(int& N, int& M, std::vector < std::pair <int, int> > Graph[]) {
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        Graph[x].emplace_back(y, cost);
    }
}
void print(int N, int Dist[]) {
    for (int i = 2; i <= N; ++i)
        g << (Dist[i] == INF ? 0 : Dist[i]) << ' ';
    g << "\n";
}
void Dijkstra(int Node, int N, int Dist[], std::vector < std::pair <int, int> > Graph[]) {
    bool use[MAX + 5] = {0};
    for (int i = 2; i <= N; ++i)
        Dist[i] = INF;
    Dist[1] = 0;
    int min, Xcopy = 0;
    for (int i = 1; i <= N; ++i) {
        min = INF;
        for (int j = 1; j <= N; ++j)
            if (!use[j] and Dist[j] < min)
                    min = Dist[j], Xcopy = j;
        use[Xcopy] = true;
        for (auto edge : Graph[Xcopy])
            if(Dist[edge.first] > Dist[Xcopy] + edge.second)
                Dist[edge.first] = Dist[Xcopy] + edge.second;
    }
}