#include <bits/stdc++.h>
 struct repRang{
    int rep;
    int rang;
};
class Edge{
public:
    int i, j, cost;
    Edge(int _i, int _j, int _cost) : i(_i), j(_j), cost(_cost){}

     friend bool operator<(const Edge& e1, const Edge& e2)
    {
        return e1.cost < e2.cost;
    }
};
const int nmax = 100005;
using namespace std;

class Graph{
   int V, E;
   vector<pair<int, int>> adj[nmax];
   bool directed, weighted;
   static int findRep(repRang*, int);
   static void reunion(repRang*, int, int);
public:
   static void disjoint();
   Graph(bool, bool);
   void build(ifstream&);
   void Kruskal(ofstream&);
   void BellmanFord(ofstream&);
};
Graph::Graph(bool _directed, bool _weighted) : directed(_directed), weighted(_weighted){}
int Graph::findRep(repRang* info, int x){
        if(x == info[x].rep)
            return x;
        return (info[x].rep = findRep(info, info[x].rep));
}
void Graph::reunion(repRang* info, int x, int y){
    int repX = findRep(info, x);
        int repY = findRep(info, y);
        if(info[repX].rang > info[repY].rang)
            info[repX].rep = repY;
        else
            if(info[repX].rang < info[repY].rang)
                info[repY].rep = repX;
            else
                {
                    info[repX].rang++;
                    info[repY].rep = repX;
                }
}
void Graph::disjoint(){
        ifstream fin("disjoint.in");
        ofstream fout("disjoint.out");
        repRang* info = new repRang[nmax];

        int N, M;
        fin >> N >> M;
        for(int i = 1; i <= N; ++i)
            info[i].rep = i;

        for(int i = 1; i <= M; ++i){
            int cod, x, y;
            fin >> cod >> x >> y;
            if(cod == 2)
                if(findRep(info, x) == findRep(info, y))
                    fout << "DA\n";
                else
                    fout << "NU\n";
            else
                reunion(info, x, y);

        }
}
void Graph::build(ifstream& fin){
    fin >> V >> E;
    for(int i = 1; i <= E; ++i){
        int src, dest, cost;
        fin >> src >> dest;
        adj[src].push_back(make_pair(dest, 0));
        if(weighted){
            fin >> cost;
            adj[src][adj[src].size() - 1].second = cost;
        }
        if(!directed)
            adj[dest].push_back(make_pair(src, cost));

    }
}
void Graph::Kruskal(ofstream& fout){
        vector<pair<int, int>> sol;
        repRang reps[nmax];
        vector<Edge> edges;
        for(int i = 1; i <= V; ++i)
        {
            int src = i;
            for(int j = 0; j < adj[i].size(); ++j){
                int dest = adj[i][j].first;
                int cost = adj[i][j].second;
                if(src > dest){
                    Edge temp_edge = Edge(src, dest, cost);
                    edges.push_back(temp_edge);
               }
            }
        }
        int total = 0;
        sort(edges.begin(), edges.end());
        for(int i = 1; i <= V; ++i)
        {
            reps[i].rep = i;
            reps[i].rang = 0;
        }

        int cnt = 0;
        int i = 0;
        for(;i < edges.size() && cnt <= E - 1; ++i){
            Edge temp_edge = edges[i];
            if(findRep(reps, edges[i].i) != findRep(reps, edges[i].j))
            {
                ++cnt;
                sol.push_back(make_pair(temp_edge.i, temp_edge.j));
                reunion(reps, temp_edge.i, temp_edge.j);
                total += temp_edge.cost;
            }
        }
        fout << total << '\n';
        fout << cnt << '\n';
        for(auto edg: sol){
            fout << edg.first << ' ' << edg.second << '\n';
        }
}

void Graph::BellmanFord(ofstream& fout){
    queue<int> q;
    bool inQ[nmax] = {false};
    int distMin[nmax];
    int cnt[nmax] = {0};
    distMin[1] = 0;
    for(int i = 2; i <= V; ++i)
        distMin[i] = INT_MAX / 2;
    q.push(1);
    inQ[1] = true;
    while(!(q.empty())){
        int i = q.front();
        q.pop();
        inQ[i] = false;
        for(auto ngb: adj[i]){
            int j = ngb.first;
            int cost = ngb.second;
            if(distMin[i] + cost < distMin[j]){
                distMin[j] = distMin[i] + cost;
                if(inQ[j] == false)
                    {   q.push(j);
                        inQ[j] = true;
                        ++cnt[j];
                        if(cnt[j] > V)
                            {
                                fout << "Ciclu negativ!\n";
                                return;
                            }
                    }

            }
        }
    }
    for(int i = 2; i <= V; ++i)
        fout << distMin[i] << ' ';
}

int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    Graph g(true, true);
    g.build(fin);
    g.BellmanFord(fout);
    return 0;
}