#include <stdio.h>
#include <vector>
using namespace std;

#define MAXN 50001
#define INF 1e9

struct muchie {
    int node, cost;
};

int nrnoduri, nrmuchii;
vector<muchie> graph[MAXN];

int dist[MAXN];

muchie heap[MAXN];
int grafnodheap[MAXN];
int heapsize;

inline int parinte(int index) {
    return (index-1)/2;
}
inline int copilst(int index) {
    return index*2+1;
}
inline int copildr(int index) {
    return index*2+2;
}

void upHeap(int heapIndex) {
    if (heapIndex  &&  heap[parinte(heapIndex)].cost > heap[heapIndex].cost) {
        swap(heap[parinte(heapIndex)], heap[heapIndex]);
        grafnodheap[heap[heapIndex].node] = heapIndex;
        grafnodheap[heap[parinte(heapIndex)].node] = parinte(heapIndex);
        upHeap(parinte(heapIndex));
    }
}

void downHeap(int heapIndex) {
    int stanga, dreapta, minim;
    
    minim = heapIndex;
    stanga = copilst(heapIndex);
    dreapta = copildr(heapIndex);
    
    if (stanga < heapsize  &&  heap[stanga].cost < heap[minim].cost) {
        minim = stanga;
    }
    if (dreapta < heapsize  &&  heap[dreapta].cost < heap[minim].cost) {
        minim = dreapta;
    }
    
    if (minim != heapIndex) {
        swap(heap[heapIndex], heap[minim]);
        grafnodheap[heap[heapIndex].node] = heapIndex;
        grafnodheap[heap[minim].node] = minim;
        
        downHeap(minim);
    }
}

void insertHeap(int nodgraf, int cost) {
    heap[heapsize] = {nodgraf, cost};
    grafnodheap[nodgraf] = heapsize;
    upHeap(heapsize++);
}

void eraseHeap(int graphNode) {
    int heapIndex;
    
    heapIndex = grafnodheap[graphNode];
    grafnodheap[graphNode] = -1;
    heap[heapIndex] = heap[heapsize-1];
    grafnodheap[heap[heapIndex].node] = heapIndex;
    heapsize--;
    
    downHeap(heapIndex);
    upHeap(heapIndex);
}

void updateHeap(int graphNode, int cost) {
    int heapIndex;
    
    heapIndex = grafnodheap[graphNode];
    heap[heapIndex].cost = cost;
    
    upHeap(heapIndex);
    downHeap(heapIndex);
}

inline bool isInHeap(int graphNode) {
    return grafnodheap[graphNode] != -1;
}

inline const muchie& findInHeap(int nodgraf) {
    return heap[grafnodheap[nodgraf]];
}

inline const muchie& topHeap() {
    return heap[0];
}

inline bool emptyHeap() {
    return heapsize == 0;
}

void dijkstra(int node) {
    int i;
    muchie top;
    
    for (i=0; i<nrnoduri; i++) {
        grafnodheap[i] = -1;
        dist[i] = INF;
    }
    
    insertHeap(node, 0);
    dist[node] = 0;
    
    while (!emptyHeap()) {
        top = topHeap();
        eraseHeap(top.node);
        
        for (muchie edge : graph[top.node]) {
            if (dist[edge.node] > top.cost+edge.cost) {
                dist[edge.node] = top.cost+edge.cost;
                if (isInHeap(edge.node)) {
                    updateHeap(edge.node, dist[edge.node]);
                } else {
                    insertHeap(edge.node, dist[edge.node]);
                }
            }
        }
    }
}

int main() {
    FILE *fin, *fout;
    fin = fopen("dijkstra.in", "r");
    fout = fopen("dijkstra.out", "w");
    
    int i, x, y, c;
    
    fscanf(fin, "%d%d", &nrnoduri, &nrmuchii);
    for (i=0; i<nrmuchii; i++) {
        fscanf(fin, "%d%d%d", &x, &y, &c);
        x--;
        y--;
        graph[x].push_back({y, c});
    }
    
    dijkstra(0);
    
    for (i=1; i<nrnoduri; i++) {
        if (dist[i] == INF) {
            fprintf(fout, "0 ");
        } else {
            fprintf(fout, "%d ", dist[i]);
        }
    }
    
    fclose(fin);
    fclose(fout);
    return 0;
}