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

using namespace std;

const int INF = 50000003;
const int MAX = 50003;

struct muchie
{
    int nod, cost;
};

int n, m, drum[MAX];

bool comp(int a, int b)
{
    return drum[a] > drum[b];
}
muchie make_muchie(int nod, int cost)
{
    muchie m1;
    m1.nod = nod;
    m1.cost = cost;
    return m1;
}

vector<muchie> v[MAX];
vector<int> heap;

void dij(int sursa);

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int a, b, c;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        v[a].push_back(make_muchie(b, c));
    }
    for(int i=1; i<=n; i++)
        drum[i] = INF;
    dij(1);
    for(int i=2; i<=n; i++)
        if(drum[i] >= INF)
            printf("0 ");
        else
            printf("%d ", drum[i]);
    return 0;
}
void dij(int sursa)
{
    int tata, fiu, cost;
    drum[sursa] = 0;
    heap.push_back(sursa);
    make_heap(heap.begin(), heap.end(), comp);

    while(heap.size())
    {
        tata = heap[0];
        if(drum[tata] >= INF) break;
        pop_heap(heap.begin(), heap.end(), comp); heap.pop_back();

        vector<muchie>::iterator it;
        for(it=v[tata].begin(); it!=v[tata].end(); ++it)
        {
            fiu = it -> nod;
            cost = it -> cost;
            if(drum[fiu] > drum[tata] + cost)
            {
                drum[fiu] = drum[tata] + cost;
                heap.push_back(fiu); push_heap(heap.begin(), heap.end(), comp);
            }
        }
    }
}