#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 50005
#define MMAX 250005
#define INF 99999999
using namespace std;

int h[NMAX], positions[NMAX], drum[NMAX]; // H[] - stores values by their read order
int hsize;
int n, m;
vector<pair<int, int> > graph[NMAX];

int left(int father)
{
    return father*2;
}

int right(int father)
{
    return father*2+1;
}

// father = index in H, H[father] returns the read order
void shift(int H[], int N, int father)
{
    int son;
    do
    {
        son = 0;
        if(left(father) <= N)
        {
            son = left(father);
            if(right(father) <=N
                && drum[H[right(father)]] < drum[H[left(father)]])
                    son = right(father);
            if(drum[H[son]] >= drum[H[father]])
                son = 0;
        }
        if (son)
        {
            swap(H[son], H[father]);
            swap(positions[H[son]], positions[H[father]]);
            father = son;
        }

    } while(son);
}

void boost(int H[], int N, int son)
{
    int father = son>>1;

    while (father && drum[H[father]] > drum[H[son]])
    {
        swap(H[father], H[son]);
        swap(positions[H[son]], positions[H[father]]);

        son = father;
        father = son>>1;
    }
}

void dijkstra()
{
    for(int i=2; i<=n; ++i)
    {
        drum[i] = INF;
    }
    h[++hsize] = 1;
    positions[1] = 1;

    while(hsize)
    {
        int minim = h[1];

        swap(h[1], h[hsize]);
        positions[h[1]] = 1;
        positions[h[hsize--]] = 0;

        shift(h, hsize, 1);

        for(int i=0; i<graph[minim].size(); ++i)
        {
            int node = graph[minim][i].first;
            int cost = graph[minim][i].second;
            if (drum[minim]+cost < drum[node])
            {
                drum[node] = drum[minim] + cost;
                if (!positions[node])
                {
                    h[++hsize] = node;
                    positions[node] = hsize;
                    boost(h, hsize, hsize);
                }
                else
                {
                    boost(h, hsize, positions[node]);
                }
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d%d", &n, &m);

    int x,y,c;
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d%d", &x, &y, &c);
        graph[x].push_back(make_pair(y, c));
    }

    dijkstra();

    for(int i=2; i<=n; ++i)
    {
        printf("%d ", drum[i]);
    }

    return 0;
}