#include <iostream>

#include <fstream>

#include <list>



using namespace std;



ifstream f("dijkstra.in");

ofstream g("dijkstra.out");



int n,m;

list <int> adj[50100];

list <int> cost[50100];

int dist[50100];

int frecv[50100];

bool incoada[50100];

int c[10000000];



void bell(int source)

{

    for(int i=1; i<=n; ++i)

        dist[i]=1<<30;

    dist[source]=0;

    c[1]=source;

    incoada[source]=1;

    int inc,sf;

    inc=sf=1;

    while(inc<=sf)

    {

        int nc=c[inc];

        incoada[nc]=0;

        if(frecv[nc]>=n)

        {

            g<<"Ciclu negativ!";

            return ;

        }

        list <int> :: iterator i,j;

        for(i=adj[nc].begin(),j=cost[nc].begin(); i!=adj[nc].end(); ++i,++j)

        {

            int u=*i;

            int cat=*j;

            if(dist[u]>dist[nc]+cat)

            {

                dist[u]=dist[nc]+cat;

                frecv[u]++;

                if(!incoada[u])

                {

                    c[++sf]=u;

                    incoada[u]=1;

                }

            }



        }

        ++inc;

    }

    for(int i=2; i<=n; ++i)
    if(dist[i]!=(1<<30))
        g<<dist[i]<<' ';
        else g<<0<<' ';

}



int main()

{
    f>>n>>m;

    for(int i=1; i<=m; ++i)

    {

        int a,b,c;

        f>>a>>b>>c;

        adj[a].push_back(b);

        cost[a].push_back(c);

    }

    bell(1);



    return 0;

}