#include <stdio.h>
#include <vector>
#include <utility>
#define nmax 50010
#define inf 0x3f3f3f3f
using namespace std;
int n,m,i,j,nr,x,y,z,d[nmax],heap[nmax];
vector < pair <int,int> > g[nmax];
void heapup(int v)
{
    int x=heap[v];
    while (v>1 && d[heap[v]]<d[heap[v/2]]) {
        swap(heap[v],heap[v/2]); v=v/2;
    }
    heap[v]=x;
}
void heapdown(int v)
{
    int w=v*2;
    while (w<=nr) {
        if (w+1<=nr && d[heap[w]]>d[heap[w+1]]) w++;
        if (d[heap[v]]>d[heap[w]]) swap(heap[v],heap[w]); else break;
        v=w; w=w*2;
    }
}
void delete_heap() {
    swap(heap[1],heap[nr]); nr--; heapdown(1);
}
int main() {
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++) {
    scanf("%d %d %d",&x,&y,&z);
    g[x].push_back(make_pair(y,z));
}
for (i=1;i<=n;i++) { d[i]=inf; heap[i]=i; }
d[1]=0; nr=n;
while (nr>0) {
    x=heap[1]; delete_heap();
    for (unsigned int i=0;i<g[x].size();i++)
        if (d[x]+g[x][i].second<d[g[x][i].first]) {
            d[g[x][i].first]=d[x]+g[x][i].second; heapup(g[x][i].first);
    }
}
for (i=2;i<=n;i++) printf("%d ",d[i]);
return 0;
}