#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;

ifstream fin("dijkstra.in");

class Dijkstra
{
    int V;
    int  src;
    int **graph;
public:
    Dijkstra(int noduri, int start)
    {
        V = noduri;
        src = start;
        int m, a, b, c;
        fin>>m;
        graph = new int *[V+1];

        for(int i = 0; i <= V; i++)
            graph[i] = new int[V+1];

        for(int i = 0; i <= V; i++)
            for(int j = 0; j <= V; j++)
                graph[i][j] = 0;

        for(int i = 0; i < m; i++)
        {
            fin>>a>>b>>c;
            graph[a][b] = c;
        }

        dijkstra(graph, src);

    }
    int minDistance(int dist[], bool sptSet[])
    {
        int minn = INT_MAX, mini;

        for (int v = 1; v <= V; v++)
            if (sptSet[v] == false && dist[v] <= minn)
                minn = dist[v], mini = v;

        return mini;
    }

    void printSolution(int dist[])
    {
        ofstream fout("dijkstra.out");
        for (int i = 1; i <= V; i++)
            //if(dist[i] != INT_MAX && i != src)
                cout<<dist[i]<<" ";
            //else if(i != src)
                //fout<<"0 ";
        fout.close();
    }


    void dijkstra(int **graph, int src)
    {
        int dist[V+1];

        bool sptSet[V+1];

        for (int i = 0; i <= V; i++)
            dist[i] = INT_MAX, sptSet[i] = false;

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {

            int u = minDistance(dist, sptSet);


            sptSet[u] = true;


            for (int v = 1; v <= V; v++)
                if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                        && dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }


        printSolution(dist);
    }

    ~Dijkstra()
    {

        for(int i = 0; i < V; i++)
            delete[] graph[i];
        delete[] graph;

        fin.close();
    }
};
int main()
{
    int n;
    fin>>n;
    Dijkstra A(n, 1);

    return 0;
}