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

#define INF (1<<29) - 1

typedef std::pair<int, int> edge;

class comparaPrioritati {
    public:
    bool operator()(edge const &p1, edge const &p2)
    {
        if (p1.second > p2.second)
            return true;
        return false;
    }
};

std::vector<int> shortest_path_Dijkstra(const std::vector<std::vector<edge> >& graph, const int source) {
    std::priority_queue <edge, std::vector<edge>, comparaPrioritati> coadaDePrioritati;
    std::vector<int> dist(graph.size() + 1, INF);
    std::vector<int> viz(graph.size() + 1, 0);
    dist[source] = 0;
    edge act;
    coadaDePrioritati.push(std::make_pair(source, 0));
    while (!coadaDePrioritati.empty()) {
        act = coadaDePrioritati.top();
        viz[act.first] = 1;
        for (int i = 0; i < graph[act.first].size(); i++) {
            if (graph[act.first][i].second != INF && viz[graph[act.first][i].first] == 0) {
                int aux;
                aux = act.second + graph[act.first][i].second;
                if(aux < dist[graph[act.first][i].first]) {
                    dist[graph[act.first][i].first] = aux;
                    coadaDePrioritati.push(std::make_pair(graph[act.first][i].first, aux));
                }
            }
        }
        coadaDePrioritati.pop();
    }
    return dist;
}

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

int main()
{
    int n, m, start;
    f >> n >> m;
    std::vector<std::vector<edge> > graf(n + 1);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        f >> a >> b >> c;
        graf[a].push_back(std::make_pair(b, c));
    }
    for(int i = 1; i < graf.size(); i++) {
        std::cout<<i<<": \n";
        for(int j = 0; j < graf[i].size(); j++) {
            std::cout<<"\t"<<graf[i][j].first << " " << graf[i][j].second<<"\n";
        }
    }

    std::vector<int> dist = shortest_path_Dijkstra(graf, 1);
    for(int i = 1; i < dist.size(); i++) {
        if(i != 1 && dist[i] != INF)
            g<<dist[i]<<" ";
    }

    return 0;
}