#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define maxn 50001
using namespace std;

//ifstream in("bellmanford.in");
//ofstream out("bellmanford.in");

int n,m;
vector < pair<int,int> > Graf[maxn];
int best[maxn];
bool viz[maxn];
int ct[maxn];
struct cmp
{
    inline bool operator () (const int &A, const int &B)
    {
        return best[A] > best[B];
    }
};
priority_queue <int ,vector <int>, cmp> Q;




int Bellmanford()
{
memset(best,0x3f,sizeof(best));
vector < pair<int,int> > :: iterator it;
best[1]=0;
Q.push(1);
while(!Q.empty())
{
int now;
now=Q.top();
Q.pop();
viz[now]=0;
for(it=Graf[now].begin();it!=Graf[now].end();it++)
    if(best[now]+it->second < best[it->first] )
    {
        best[it->first]=best[now]+it->second;

        if(!viz[it->first])
        {
            viz[it->first]=1;
            Q.push(it->first);
            ++ct[it->first];
            if(ct[it->first]>=n)
                {
                    cout<<"Ciclu negativ!";
                    exit(0);
                }
        }

    }

}

}

int main()
{
    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out", "w", stdout);
    cin>>n>>m;
    char x,y,z;
    while(m--)
    {
        cin>>x>>y>>z;
        Graf[x-'0'].push_back(make_pair(y-'0',z-'0'));
    }
    Bellmanford();
    for(int i=2;i<=n;i++)
        cout<<best[i]<<" ";

    return 0;
}