#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
#define INF 1<<30
#define nMAX 50005

vector< pair<int,int> > adj[nMAX];
vector<int> adj_t[nMAX];
int N,M;


void init();
void solve();
long check_negativ();

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    in>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        adj[x].push_back(make_pair(y,c));
        adj_t[x].push_back(y);
    }
    in.close();

    queue<int> Q;
    bitset<nMAX> in_queue(false);
    vector<int> dist(nMAX,INF) , cnt_in_queue(nMAX,0);
    bool negative_cycle=false;
    dist[1]=0;
    Q.push(1);
    in_queue[1].flip();
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        in_queue[x]=false;
        vector< pair<int,int> >::iterator it;
        vector< pair<int,int> >::iterator end;
        end=adj[x].end();
        for(it=adj[x].begin();it!=end;++it)
            if(dist[x]<INF)
                if(dist[it->first]>dist[x]+it->second)
                {
                    dist[it->first]=dist[x]+it->second;
                    if(!in_queue[it->first])
                    {
                        if(cnt_in_queue[it->first] > N)
                        {
                            out<<"Ciclu negativ!\n";
                            return 0;
                        }
                        else
                        {
                            Q.push(it->first);
                            in_queue[it->first]=true;
                            cnt_in_queue[it->first]++;
                        }
                    }
                }

    }

    for(int i=2;i<=N;i++)
        out<<dist[i]<<" ";
    out.close();
    in.close();
    return 0;
}