#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 50005
#define MAXM 250005
#define INF 250000001

vector<pair <int, int> >v[MAX];

int d[MAX], heap[MAX], lv[MAX];
void del(int poz), upheap(int poz), downheap(int poz);
int n, m, nh;
int main()
{

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i, a, b, w, bnod;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&w);
        v[a].push_back(make_pair(b,w));
        lv[a]++;
    }
    for(i=2; i<=n; i++) d[i] = INF;
    heap[++nh] = 1;
    while(1)
    {
        if(nh==0)
            break;
        bnod = heap[1];
        del(1);
        for(i=0; i<lv[bnod]; i++)
        {
            if(d[bnod] + v[bnod][i].second < d[v[bnod][i].first]){
                d[v[bnod][i].first]=d[bnod] + v[bnod][i].second;
                heap[++nh] = v[bnod][i].first;
                upheap(nh);
            }
        }
    }
    for(i=2; i<=n; i++)
    {
        if(d[i] == INF)
            printf("0 ");
        else
            printf("%d ",d[i]);
    }
    printf("\n");
    return 0;
}
void upheap(int poz)
{
    int tata;
    if(poz == 1) return;
    tata = poz/2;
    if(d[tata] > d[poz])
    {
        swap(heap[tata],heap[poz]);
        upheap(tata);
    }
}
void del(int poz)
{
    swap(heap[1],heap[nh]);
    nh--;
    downheap(1);
}
void downheap(int poz)
{
    int fiu;
    if(poz*2 > nh) return;
    fiu = poz*2+(poz*2+1<nh and d[poz*2]>d[poz*2+1]);
    if(d[poz] > d[fiu])
    {
        swap(heap[poz],heap[fiu]);
        downheap(fiu);
    }
}