#include <cstdio>
#include <vector>
#include <queue>
#define add push_back
#define nmax 50000+5
using namespace std;

struct muchie
{
    int destinatie;
    int cost;

    muchie(int d = 0, int c = 0): destinatie(d), cost(c)
    {

    }
};

vector<muchie> graf[nmax];
int pas[nmax];

struct cmp
{
    bool operator()(const int & a, const int & b)
    {
        return pas[a] > pas[b];
    }
};

priority_queue<int, vector<int>, cmp> heap;
int n, m;

void dijkstra()
{
    pas[1] = 1;
    heap.push(1);
    int curent, vecin;
    int k;

    while (!heap.empty())
    {
        curent = heap.top();
        heap.pop();

        for (k = 0; k < graf[curent].size(); k++)
        {
            vecin = graf[curent][k].destinatie;
            if (pas[vecin] == 0)
            {
                pas[vecin] = pas[curent] + graf[curent][k].cost;
                heap.push(vecin);
            }
        }
    }
}

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

    int index;
    int a, b, c;
    scanf("%d%d", &n, &m);

    for (index = 1; index <= m; index++)
    {
        scanf("%d%d%d", &a, &b, &c);
        graf[a].add(muchie(b, c));
    }

    dijkstra();

    for (index = 2; index <= n; index++)
        if (pas[index] != 0)
            printf("%d ", pas[index]-1);
        else
            printf("%d ", 0);
    return 0;
}