#include <cstdio>
#include <deque>
#include <vector>
#define NMAX 50005
#define MMAX 250005
#define INF 1e9

using namespace std;

FILE *f = freopen("dijkstra.in", "r", stdin);
FILE *g = freopen("dijkstra.out", "w", stdout);

struct node{
    int vertex;
    int cost;
    node *next;
};

node *a[NMAX];
int n, m, first, last;
int  dist[NMAX];

vector <int> cntQueue(NMAX, 0);
deque <int> myQueue;
bool negCycle = false;
bool inQueue[NMAX];
void insertBeginning(node *& head, int cost, int vertex) {
    node *tmp = new node;
    tmp -> vertex = vertex;
    tmp -> cost = cost;
    tmp -> next = head;
    head = tmp;
}

void readData() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i<=m; i++) {
        int v1, v2, cost;
        scanf("%d%d%d", &v1, &v2, &cost);
        insertBeginning(a[v1], cost, v2);
    }
}

void printData(node *& head) {
    node *tmp = head;
    while(tmp != NULL) {
        printf("%d ", tmp -> vertex);
        tmp = tmp -> next;
    }
}

void bellman(int start){
    inQueue[start] = true;
    myQueue.push_back(start);
    for(int i = 0; i<=n; i++)
        dist[i] = INF;
    dist[start] = 0;
    while(!myQueue.empty()){
        int currNode = myQueue.front();
        node *tmpHead = a[currNode];
        inQueue[currNode] = false;
        while(tmpHead != NULL) {
            if(dist[currNode] + tmpHead -> cost < dist[tmpHead -> vertex]) {
                dist[tmpHead -> vertex] = dist[currNode] + tmpHead -> cost;
                if(!inQueue[tmpHead -> vertex]) {

                        if(cntQueue[tmpHead -> vertex] > n) {
                            negCycle = true;
                        }
                        else {
                    myQueue.push_back(tmpHead -> vertex);
                    inQueue[tmpHead -> vertex] = true;
                    cntQueue[tmpHead -> vertex] ++;
                        }
                }
            }
            tmpHead = tmpHead -> next;
        }
        myQueue.pop_front();
    }
}
int main() {
    readData();
    bellman(1);
    if(negCycle) {
        printf("Ciclu negativ!\n");
        return 0;
    }
    for(int i = 2; i<=n; i++)
        printf("%d ", dist[i]);
        return 0;
}