#include <cstdio>
#include <vector>
#include <queue>
#define lim 50001
#define oo ((1<<30)-1)
using namespace std;


int n,m;
FILE *outFile = fopen("bellmanford.out","w");
int nr[lim];
struct nod
{
    int v;
    int cst;
}Nod;
vector<nod> graph[lim];


int cost[lim];

struct cmp
{
    bool operator()(int &a,int &b)
    {
        return cost[a] > cost[b];
    }
};
priority_queue<int, vector<int>, cmp> Q;

void citire()
{
    freopen("bellmanford.in","r",stdin);
    scanf("%d %d",&n,&m);

    for(int i =0 ; i <  m; i++)
    {
        int x;
        scanf("%d %d %d",&x,&Nod.v,&Nod.cst);
        graph[x].push_back(Nod);
    }
}

int dijkstra(int start){

    for(int i = 2 ; i <= n; cost[i] = oo, i++);
    Q.push(start);

    while(!Q.empty())
    {
        int min = Q.top();
        Q.pop();

        for(int i = 0 ; i < graph[min].size();i++)
        {
                int sum = cost[min] + graph[min][i].cst;
                if(sum < cost[graph[min][i].v])
                {
                    cost[graph[min][i].v] = sum;
                   Q.push(graph[min][i].v);
                   if(++ nr[min] > n)
                   {
                       return -1;
                   }

                }
        }


    }



}

int main()
{

    citire();
    if(dijkstra(1) == -1)
    fprintf(outFile,"Ciclu negativ!");
    else
    for(int i = 2; i <= n; i++)
    {
        if(cost[i] == oo)
        fprintf(outFile,"0 ");
        else
        fprintf(outFile,"%d ", cost[i]);
    }
    return 0;
}