#include<fstream>
#include<vector>
#include<queue>
#define INF 1<<30
#define nMAX 50002
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int N,M;
vector< pair<int,int> > much[nMAX];
bool in_queue[nMAX];
int cnt_in_queue[nMAX];

int main()
{
    in>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        much[x].push_back(make_pair(y,c));
    }
    queue<int> Q;
    vector<int> dist(nMAX,INF);
    Q.push(1);
    dist[1]=0;
    in_queue[1]=true;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        in_queue[x]=false;
        vector< pair<int,int> >::iterator it;
        for(it=much[x].begin();it!=much[x].end();it++)
        {
            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;
                    }
                    Q.push(it->first);
                    in_queue[it->first]=true;
                    cnt_in_queue[it->first]++;
                }
            }
        }
    }

    for(int i=2;i<=N;i++)
        out<<(dist[i]==INF ? dist[i] : 0)<<" ";

    return 0;
}