#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(), INF);
    std::vector<int> viz(graph.size(), 0);
    dist[source] = 0;
    edge act;
    int aux, lungimeNoua, nodDestinatie;
    unsigned int i;
    coadaDePrioritati.push(std::make_pair(source, 0));
    while (!coadaDePrioritati.empty()) {
        act = coadaDePrioritati.top();
        viz[act.first] = 1;
        for (i = 0; i < graph[act.first].size(); i++) {
            lungimeNoua = graph[act.first][i].second;
            nodDestinatie = graph[act.first][i].first;
            if (lungimeNoua != INF && viz[nodDestinatie] == 0) {
                aux = act.second + lungimeNoua;
                if (aux < dist[nodDestinatie]) {
                    dist[nodDestinatie] = aux;
                    coadaDePrioritati.push(std::make_pair(nodDestinatie, aux));
                }
            }
        }
        coadaDePrioritati.pop();
    }
    return dist;
}

std::vector<int> shortest_path_BellmanFord(const std::vector<std::vector<edge> >& graph, const int source) {
    std::vector<int> dist(graph.size(), INF);
    std::vector<bool> inQueue(graph.size(), false);
    dist[source] = 0;
    std::queue<int> coada;
    coada.push(source);
    int curr, lungimeNoua, nodDestinatie;
    while (!coada.empty()) {
        curr = coada.front();
        inQueue[curr] = false;
        coada.pop();
        for (unsigned int k = 0; k < graph[curr].size(); k++) {
            lungimeNoua = graph[curr][k].second;
            nodDestinatie = graph[curr][k].first;
            if (dist[curr] + lungimeNoua < dist[nodDestinatie]) {
                dist[nodDestinatie] = dist[curr] + lungimeNoua;
                if (!inQueue[nodDestinatie]) {
                    inQueue[nodDestinatie] = true;
                    coada.push(nodDestinatie);
                }
            }
        }
    }

    for (unsigned int j = 0; j < graph.size(); j++) {
        for (unsigned int k = 0; k < graph[j].size(); k++) {
            if (dist[j] + graph[j][k].second < dist[graph[j][k].first]) {
                printf("EROARE graful contine cicluri negative");
                return std::vector<int>();
            }
        }
    }
    return dist;
}

std::ifstream f("dijkstra.in");
FILE * g = fopen ("dijkstra.out","w");

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));
    }
    std::vector<int> dist = shortest_path_BellmanFord(graf, 1);
    for (int i = 1; i < dist.size(); i++) {
        if (i != 1)
            fprintf(g, "%d ", dist[i] != INF ? dist[i] : 0);
    }

    return 0;
}