/*
 * Graph struct
 */
//#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
struct Graph{
    const int INF=1000000000;
    struct Edge{
        ///struct for edges
        int u,v,w;
        Edge(int u,int v,int w){
            this->u=u;
            this->v=v;
            this->w=w;
        }
        Edge(int u,int v){
            this->u=u;
            this->v=v;
            this->w=1;
        }
    };
    struct Corr_Edge{
        ///struct for the correspondent node and weight for a certain edge
        int v,w;
        Corr_Edge(int v,int w){
            this->v=v;
            this->w=w;
        }
        Corr_Edge(int v) {
            this->v = v;
            this->w = 1;
        }
    };
    int nodes,edges,nr_conexe;
    bool NEG_CYCLE=false;
    vector <Edge> edge_set;
    vector <int> bfs_cost;
    vector <int> dijkstra_cost;
    vector <int> spfa_cost;
    vector <int> connected_component;
    vector <vector<Corr_Edge > >adjacency_list;
    Graph(int nodes){
        this->nodes=nodes;
        this->edges=0;
        for(int i=0;i<=nodes;i++){
            vector <Corr_Edge > v;
            adjacency_list.push_back(v);
        }
    }
    ///add edges to graph
    void add_UEdge(Edge x){
        edge_set.push_back(x);
        adjacency_list[x.u].push_back(Corr_Edge(x.v,x.w));
    }
    void add_UEdge(int u,int v,int w){
        edge_set.push_back(Edge(u,v,w));
        adjacency_list[u].push_back(Corr_Edge(v,w));
        adjacency_list[v].push_back(Corr_Edge(u,w));
    }
    void add_UEdge(int u,int v){
        edge_set.push_back(Edge(u,v));
        adjacency_list[u].push_back(Corr_Edge(v,1));
        adjacency_list[v].push_back(Corr_Edge(u,1));
    }
    void add_DEdge(int u,int v,int w){
        edge_set.push_back(Edge(u,v,w));
        adjacency_list[u].push_back(Corr_Edge(v,w));
    }
    void add_DEdge(int u,int v){
        edge_set.push_back(Edge(u,v));
        adjacency_list[u].push_back(Corr_Edge(v,1));
    }

    ///bfs
    void bfs(int source){
        vector <int> s;
        s.push_back(source);
        bfs(s);
    }
    void bfs(vector <int> source){
        if(bfs_cost.size()==0){
            for(int i=0;i<=nodes;i++){
                bfs_cost.push_back(-1);
            }
        }
        fill(bfs_cost.begin(),bfs_cost.end(),-1);
        queue <pair<int,int> >q;

        for(auto u:source) {
            q.push(make_pair(u, 0));
            bfs_cost[u]=0;
        }
        while(!q.empty()){
            auto u=q.front();
            q.pop();
            int curr=u.first,curr_cost=u.second;
            for(auto uu:adjacency_list[curr]){
                if(bfs_cost[uu.v]==-1){
                    bfs_cost[uu.v]=curr_cost+1;
                    q.push(make_pair(uu.v,curr_cost+1));
                }
            }
        }
    }
    int bfs_distance(int nod){
        return bfs_cost[nod];
    }

    ///connected_components
    void dfs_colour(int nod,int colour){
        connected_component[nod]=colour;
        for(auto u:adjacency_list[nod]){
            if(connected_component[u.v]==-1){
                dfs_colour(u.v,colour);
            }
        }
    }
    void components(){
        /// We count all components with node from 0 to nodes;
        /// Usually tasks have nodes from 1 to nodes or from 0 to nodes-1
        /// Calculating the number of components from 0 to nodes and subtracting 1 should work
        if(connected_component.size()==0){
            for(int i=0;i<=nodes;i++){
                connected_component.push_back(-1);
            }
        }else
        fill(connected_component.begin(),connected_component.end(),-1);
        nr_conexe=0;
        for(int i=0;i<=nodes;i++){
            if(connected_component[i]==-1){
                nr_conexe++;
                connected_component[i]=nr_conexe;
                dfs_colour(i,nr_conexe);
            }
        }
    }
    int nr_components(){
        return nr_conexe-1;
    }

    ///dijkstra
    void dijkstra(int source){
        vector <int> v;
        v.push_back(source);
        dijkstra(v);
    }
    void dijkstra(vector <int> source){
        if(dijkstra_cost.size()==0){
            for(int i=0;i<=nodes;i++) {
                dijkstra_cost.push_back(-1);
            }
        }
        else
            fill(dijkstra_cost.begin(),dijkstra_cost.end(),-1);
        priority_queue <pair<int,int> >pq;
        for(auto u:source){
            pq.push(make_pair(0,u));
        }
        while(!pq.empty()){
            auto u=pq.top();
            pq.pop();
            int nod=u.second;
            int cost=-u.first;
            if(dijkstra_cost[nod]!=-1)
                continue;
            dijkstra_cost[nod]=cost;
            for(auto u:adjacency_list[nod]){
                if(dijkstra_cost[u.v]==-1){
                    pq.push(make_pair(-(cost+u.w),u.v));
                }
            }
        }
    }
    int dijkstra_distance(int nod){
        return dijkstra_cost[nod];
    }

    ///spfa
    void spfa(int source){
        vector <int> v;
        v.push_back(source);
        spfa(v);
    }
    void spfa(vector <int> source){
        if(spfa_cost.size()==0){
            for(int i=0;i<=nodes;i++)
            spfa_cost.push_back(INF);
        }
        else{
            fill(spfa_cost.begin(),spfa_cost.end(),INF);
        }
        queue <int> q;
        bool inside[nodes+2];
        int viz[nodes+2];
        for(int i=0;i<=nodes;i++){
            inside[i]=false;
            viz[i]=0;
        }
        for(auto u:source){
            spfa_cost[u]=0;
            q.push(u);
            inside[u]=true;
        }
        while(!q.empty()){
            int nod=q.front();
            q.pop();
            inside[nod]=false;
            viz[nod]++;
            if(viz[nod]==nodes){
                ///negative cycle
                NEG_CYCLE=true;
                return;
            }
            for(auto u:adjacency_list[nod]){
                if(spfa_cost[u.v]>spfa_cost[nod]+u.w){
                    spfa_cost[u.v]=spfa_cost[nod]+u.w;
                    if(!inside[u.v]){
                        inside[u.v]=true;
                        q.push(u.v);
                    }
                }
            }
        }
    }
    int spfa_distance(int nod){
        return spfa_cost[nod];
    }
};


int main(){
    int n,m,s;
    cin>>n>>m;
    Graph g(n);
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g.add_DEdge(a,b,c);
    }
    g.spfa(1);
    if(g.NEG_CYCLE==true){
        cout<<"Ciclu negativ!";
    }else
    for(int i=2;i<=n;i++){
        int a=g.spfa_distance(i);
        cout<<(a)<<" ";
    }
}