#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

#define inf 9000

int N,M;

struct Node{

    Node()
    {
        dist = inf;
        parent = 0;
    }

    int dist;
    int parent;
    list<pair<int,int> > neigh;
};

vector<Node> nodes;


void dijkstra(int sursa)
{

    queue<int> qu;
    list<pair<int,int> >::iterator it;

    int i,cnode;

    for(it = nodes[sursa].neigh.begin();
        it != nodes[sursa].neigh.end(); it++)
    {
        nodes[it->first].dist = it->second;
        nodes[it->first].parent = sursa;
        qu.push(it->first);
        std::cout << "added=" << it->first << std::endl;
    }

    // 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 lui cnode
        for(it = nodes[cnode].neigh.begin();
            it != nodes[cnode].neigh.end(); it++)
        {
            if(nodes[it->first].dist > nodes[cnode].dist + it->second)
            {
                nodes[it->first].dist = nodes[cnode].dist + it->second;
                nodes[it->first].parent = cnode;
                std::cout << " changed ";
                std::cout << "new dist="<<nodes[it->first].dist;
                qu.push(it->first);
            }
        }

        // 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;

    nodes.resize(N+1);

    for(i = 1; i <= M; i++){
        in >> x >> y >> cost;
        nodes[x].neigh.push_back(pair<int,int>(y,cost));
    }

    dijkstra(1);

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

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

    return 0;
}