#include <cstdio>
#include <vector>
#define MAX_N 50001
#define inf 1001
using namespace std;
int N, M, dist[MAX_N], heap[MAX_N], poz[MAX_N], k;
vector<pair <int, int> > graph[MAX_N];
FILE *f, *g;

void swap_val(int fiu, int tata)
{
    int aux=heap[fiu];
    heap[fiu]=heap[tata];
    heap[tata]=aux;
}

void upheap(int loc)
{
    while(loc/2>=1 && dist[heap[loc/2]]>dist[heap[loc]])
    {
        poz[heap[loc/2]]=loc;
        poz[heap[loc]]=loc/2;
        swap_val(loc/2, loc);
        loc=loc/2;
    }
}

void downheap(int loc)
{
    if(loc*2<=k && (dist[heap[loc*2]]<dist[heap[loc]] || dist[heap[loc*2+1]]<dist[heap[loc]]))
    {
        if(dist[heap[loc]]>dist[heap[loc*2]] && dist[heap[loc*2]]<dist[heap[loc*2+1]])
        {
            poz[heap[loc]]=loc*2;
            poz[heap[loc*2]]=loc;
            swap_val(loc, loc*2);
        }
        else
        {
            poz[heap[loc*2+1]]=loc;
            poz[heap[loc]]=loc*2+1;
            swap_val(loc, loc*2+1);
        }
    }
}

int main()
{
    int x, y, c, nod, vecin, cost;

    f = fopen("dijkstra.in", "r");
    g = fopen("dijkstra.out", "w");
    fscanf(f, "%d%d", &N, &M);
    for(int i=0; i<M; i++)
    {
        fscanf(f, "%d%d%d", &x, &y, &c);
        graph[x].push_back(make_pair(y, c));
    }

    for(int i=2; i<=N; i++)
        dist[i]=inf;

    k++;
    heap[1]=1;
    for(int i=2; i<=N; i++)
    {
        k++;
        heap[k]=i;
        poz[i]=k;
    }

    while(heap[1]!=0)
    {
        nod=heap[1];
        heap[1]=heap[k];
        poz[heap[1]]=1;
        k--;
        downheap(1);
        for(int i=0; i<graph[nod].size(); i++)
        {
            vecin=graph[nod][i].first;
            cost=graph[nod][i].second;
            if(dist[vecin]>dist[nod]+cost)
            {
                dist[vecin]=dist[nod]+cost;
                upheap(poz[vecin]);
            }
        }
    }

    for(int i=2; i<=N; i++)
        fprintf(g, "%d ", dist[i]);

    fclose(f);
    fclose(g);
    return 0;
}