#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

#define inf 9000

#define CONTAINER 500

int N,M;
int graph[CONTAINER][CONTAINER];
int dist[CONTAINER];
int parent[CONTAINER];
//bool selectat[5000];

void dijkstra(int sursa)
{

    queue<int> qu;

    int i,cnode;
    for(i = 1; i <= N; i++)
    if(graph[sursa][i] != inf)
    {
        dist[i] = graph[sursa][i];
        parent[i] = sursa;
        qu.push(i);
        //selectat[i] = true;
        std::cout << "added=" << i << std::endl;
    }

    //Relaxeaza
    while(!qu.empty())
    {
        cnode = qu.front();
        qu.pop();

        std::cout << "for "<< cnode<<" exploring:" << std::endl;

        //selectat[cnode] = true;

        //Vecinii
        for(i = 1; i <= N; i++)
        {
            if(graph[cnode][i] != inf){
                std::cout << i;
                if( dist[i] > dist[cnode] + graph[cnode][i]){
                    dist[i] = dist[cnode] + graph[cnode][i];
                    parent[i] = cnode;
                    std::cout << " changed ";
                    std::cout << "new dist="<<dist[i];
                    qu.push(i);
                }

                std::cout << std::endl;
            }

        }
    }
}


int main(){

    int i,j,cost,x,y;

    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    in >> N >> M;

    if(N -1 > CONTAINER || M-1 > CONTAINER)
        return 0;

    for(i = 1; i <= N; i++){
        dist[i] = inf;

        for(j = 1; j <= N; j++)
        {
            graph[i][j] = inf;
        }
    }


    for(i = 1; i <= M; i++){
        in >> x >> y >> cost;
        graph[x][y] = cost;
    }

    dijkstra(1);

    for(i = 2; i <= N; i++)
        if(dist[i] == inf)
            out << 0 << " ";
        else
            out << dist[i] << " ";

    in.close();
    out.close();

    return 0;
}