# include <fstream>
# include <vector>
# include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,i,x,y,z,w[50001];
vector<pair<int,int> > v[50001];
queue<int> q;
bool b[50001];
void read()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
         {
          f>>x>>y>>z;
          v[x].push_back(make_pair(y,z));
          w[x]=w[y]=50000001;
         }
}
void Bellman_Ford()
{
    int d;
    long long p=0,k=(n-1)*m;
    w[1]=0;
    q.push(1);
    b[1]=1;
    while(!q.empty()&&p<=k)
           {
            x=q.front();
            q.pop();
            b[x]=0;
            d=v[x].size();
            for(i=0;i<d;i++)
                if(w[v[x][i].first]>w[x]+v[x][i].second)
                    {
                     w[v[x][i].first]=w[x]+v[x][i].second;
                     p++;
                     if(!b[v[x][i].first])
                        {
                         q.push(v[x][i].first);
                         b[v[x][i].first]=1;
                        }
                    }
           }
}
void write()
{
    if(q.empty())
        for(i=2;i<=n;i++)
             g<<w[i]<<" ";
    else
      g<<"Ciclu negativ!";
}
int main()
{
    read();
    Bellman_Ford();
    write();
    f.close();
    g.close();
    return 0;
}