#include <cstdio>
        #include <cstring>
        #include <vector>
        #include <queue>
        #define INF 1000000
        using namespace std;
        struct bellmanford
        {
            vector <int> nod;
            vector <int> cost;
        };
        bellmanford g[50001];
        queue <int> q;
        bool used[50001];
        int Cost[50001], nrit[50001];
        int main()
        {
            int n, m, x, y, z, nod, i;
            freopen("bellmanford.in","r",stdin);
            freopen("bellmanford.out","w",stdout);
            scanf("%d%d",&n,&m);
            for (i=1; i<=m; i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                g[x].nod.push_back(y);
                g[x].cost.push_back(z);
            }
            for (i=2; i<=n; i++) Cost[i]=INF;
            q.push(1); used[1]=true;
            while (!q.empty())
            {
                nod=q.front();
                q.pop();
                used[nod]=false;
                for (i=0; i<g[nod].nod.size(); i++)
                {
                    if (Cost[nod]+g[nod].cost[i]<Cost[g[nod].nod[i]])
                    {
                        Cost[g[nod].nod[i]]=Cost[nod]+g[nod].cost[i];
                        if (!used[g[nod].nod[i]])
                        {
                            used[g[nod].nod[i]]=true;
                            q.push(g[nod].nod[i]);
                            nrit[g[nod].nod[i]]++;
                            if (nrit[g[nod].nod[i]]>n)
                            {
                                printf("Ciclu negativ!");
                                return 0;
                            }
                        }
                    }
                }
            }
            for (i=2; i<=n; i++) printf("%d ",Cost[i]);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }