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

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

class graph{
    const int INF = (1<<31)-1;
    vector< vector < int > > Ad;
    vector< vector < int > > EdgeValue;
    const int nodes;
    int edges = 0;

    struct disjoint_set{
        int parent, sz;
    };
    struct edge{
        int x, y, v;

        bool operator < ( const edge & E ) {
            return v < E.v;
        }
    };

    int Find( vector < disjoint_set > & ds, int x);
    void Union(vector < disjoint_set > & ds, int x, int y);

public:
    graph( int n):nodes(n){ Ad.resize(nodes+1); }
    graph( int n, int m, vector < vector < int > > & ad ) : nodes(n), edges(m){
        Ad.resize(nodes+1);
        for( int i = 1; i <= nodes; ++i ){
            for( int j = 0; j < ad[i].size(); ++j)
                Ad[i].push_back(ad[i][j]);
        }
    }
    graph( int n, int m, vector < vector < int > > & ad, vector < vector < int > > & values ) : nodes(n), edges(m){
        Ad.resize(nodes+1);
        EdgeValue.resize(nodes+1);
        for( int i = 1; i <= nodes; ++i )
            for( int j = 0; j < ad[i].size(); ++j){
                Ad[i].push_back(ad[i][j]);
                EdgeValue[i].push_back(values[i][j]);
        }
    }

    void addEdge(int x, int y, bool oriented);
    void DFS( int nod, bool vis[] );
    void BFS( int nod );
    int ConnectedComponents();
    void readWeighted();
    void Kruskal();
    void Dijkstra( int nod );
    void BellmanFord( int nod );
};

void graph::addEdge(int x, int y, bool oriented){
    Ad[x].push_back( y );
    if( oriented == false )
        Ad[y].push_back(x);
    edges++;
}
void graph::DFS( int nod, bool vis[] ){
    vis[nod] = 1;
    for( int i = 0; i < Ad[nod].size(); ++i ){
        int w = Ad[nod][i];
        if( vis[w] == 0 )DFS(w,vis);
    }
}
void graph::BFS( int nod ){

    queue < int > Q;

    int dist[nodes] = {0};
    Q.push(nod);
    int x;

    while( !Q.empty() ){
        x = Q.front();
        Q.pop();

        for( int i = 0; i < Ad[x].size(); ++i ){
            int w = Ad[x][i];

            if( dist[w] == 0 && w != x && w != nod ){
                dist[w] = dist[x] + 1;
                Q.push(w);
            }
        }
    }

    for( int i = 1; i <= nodes; ++i )
        if( dist[i] != 0 || i == nod )fout << dist[i] << ' ';
        else fout << "-1 ";
}
int graph::ConnectedComponents(){
    int nr = 0;
    bool vis[nodes] = {0};
    for( int i = 1; i <= nodes; ++i )
        if( vis[i] == 0 ){
            DFS(i,vis);
            nr++;
        }
    return nr;
}
int graph::Find( vector < disjoint_set > & ds, int x){

    int aux, root = x;
    while( ds[root].parent != root ) root = ds[root].parent;
    while( ds[x].parent != x ){
        aux = ds[x].parent;
        ds[x].parent = root;
        x = aux;
    }
    return root;
}
void graph::Union(vector < disjoint_set > & ds, int x, int y){

    int root_x = Find(ds,x);
    int root_y = Find(ds,y);

    if( ds[root_x].sz >= ds[root_y].sz ){
        ds[root_x].sz += ds[root_y].sz;
        ds[root_y].parent = root_x;
    }
    else{
        ds[root_y].sz += ds[root_x].sz;
        ds[root_x].parent = root_y;
    }
}
void graph::Kruskal(){
    vector < disjoint_set > disjoint_sets;
    vector < edge > E;

    int M;
    fin >> M;
    int x, y, v;

    disjoint_sets.resize(nodes+1);
    for( int i = 1; i <= nodes; ++i )
        disjoint_sets[i] = {i,1};

    for( int i = 1; i <= M; ++i ){
        fin >> x >> y >> v;
        E.push_back({x,y,v});
    }

    sort( E.begin(), E.end() );

    vector < pair < int , int > > Sol;
    int TotalValue = 0, edges_nr = 0;

    for( int i = 0; i < M && edges_nr < nodes; ++i ){
        int root_x = Find(disjoint_sets, E[i].x);
        int root_y = Find(disjoint_sets, E[i].y);
        if( root_x != root_y ){
            edges_nr++;
            Sol.push_back( {E[i].x, E[i].y} );
            TotalValue += E[i].v;
            Union(disjoint_sets, root_x, root_y );
        }
    }
    fout << TotalValue << '\n';

    fout << Sol.size() << '\n';
    for( int i = 0; i < Sol.size(); ++i )
        fout << Sol[i].first << ' ' << Sol[i].second << '\n';
}
void graph::Dijkstra(int nod){
    priority_queue< pair < int, int >, vector < pair <int, int> >, greater < pair < int, int > >  > H;
    vector < int > dist(nodes+1,INF);
    vector < bool > vis(nodes+1, 0);
    dist[nod] = 0;
    H.push( {0,nod} );

    while( !H.empty() ){
        nod = H.top().second;
        H.pop();

        if( vis[nod] ) continue;
        else vis[nod] = 1;

        for( int i = 0; i < Ad[nod].size(); ++i ){

            int w = Ad[nod][i];
            int dw = EdgeValue[nod][i];

            if( dist[w] > dist[nod] + dw ){
                dist[w] = dist[nod] + dw;
                H.push( { dist[w], w } );
            }
        }
    }

    for( int i = 2; i <= nodes; ++i )
        (dist[i] != INF) ? fout << dist[i] << ' ': fout << 0 << ' ';
}
void graph::BellmanFord( int src ){
    vector < int > dist(nodes+1, INF);
    vector < int > visCount(nodes+1, 0);
    vector < bool > inQ( nodes+1, 0);
    queue < int > Q;

    dist[src] = 0;
    Q.push( src );

    int nod;
    bool negativeCicle = false;

    while( !Q.empty() && !negativeCicle ){
        nod = Q.front();
        Q.pop();
        inQ[nod] = false;

        for( int i = 0; i < Ad[nod].size(); ++i ){
            int w = Ad[nod][i];
            int dw = EdgeValue[nod][i];

            if( dist[w] > dist[nod] + dw ){
                dist[w] = dist[nod] + dw;
                //cout << nod << ' ' << w << ' ' << dist[w] << '\n';

                if( inQ[w] == false ){
                    inQ[w] = true;
                    Q.push( w );
                }

                visCount[w]++;
                if( visCount[w] == nodes ){
                    negativeCicle = true;
                    break;
                }
            }
        }
    }

    if( negativeCicle == true )
        fout << "Ciclu negativ!\n";
    else{
        for( int i = 1; i <= nodes; ++i )
            if( i != src )
                fout << dist[i] << ' ';
        fout << '\n';
    }
}
int main()
{
    int N, M, x, y, v;
    fin >> N >> M;

    vector < vector < int > > Ad(N+1), Values(N+1);

    for( int i = 1; i <= M; ++i ){
        fin >> x >> y >> v;
        Ad[x].push_back( y );
        Values[x].push_back( v );
    }

    graph G(N, M, Ad, Values);
    G.BellmanFord( 1 );

    return 0;
}