#include <cstdio>
#include <vector>

using namespace std;

struct edge{int node; int cost;};
const int MAXN = 50002;
const int INF = 0x3f3f3f3f;

vector<edge> g[MAXN];
int heap[MAXN];
int in_heap[MAXN];
int d[MAXN];
bool vis[MAXN];
int heap_size = 0;

void swapValues(int a, int b)
{
    int t = heap[a];
    heap[a] = heap[b];
    heap[b] = t;
    in_heap[heap[a]] = a;
    in_heap[heap[b]] = b;
}

void addToHeap(int node)
{
    if (in_heap[node])
    {
        int i = in_heap[node];
        while (i > 1 && d[heap[i]] < d[heap[i/2]])
        {
            swapValues(i, i/2);
            i = i/2;
        }
    }
    else
    {
        heap[++heap_size] = node;
        in_heap[node] = heap_size;
        int i = heap_size;
        while (i > 1 && d[heap[i]] < d[heap[i/2]])
        {
            swapValues(i, i/2);
            i = i/2;
        }
    }
}

void deleteTop()
{
    in_heap[heap[1]] = 0;
    heap[1] = heap[heap_size];
    in_heap[heap[1]] = 1;
    heap[heap_size] = 0;
    heap_size--;
    int i = 1;
    int vmin;
    while (1)
    {
        vmin = i;
        if (2*i <= heap_size && d[heap[2*i]] < d[heap[vmin]])
            vmin = 2*i;
        if (2*i+1 <= heap_size && d[heap[2*i+1]] < d[heap[vmin]])
            vmin = 2*i+1;
        if (vmin != i)
        {
            swapValues(i, vmin);
            i = vmin;
        }
        else
            break;
    }
}

int main()
{
    FILE *in = fopen("dijkstra.in", "r");
    FILE *out = fopen("dijkstra.out", "w");

    int n, m;
    fscanf(in, "%d%d", &n, &m);

    int x, y, c;
    edge e;
    while (m--)
    {
        fscanf(in, "%d%d%d", &x, &y, &c);
        e.node = y;
        e.cost = c;
        g[x].push_back(e);
    }

    for (int i = 2; i <= n; i++)
        d[i] = INF;

    addToHeap(1);
    int node;
    while (heap_size > 0)
    {
        node = heap[1];
        vis[node] = 1;
        deleteTop();
        for (unsigned i = 0; i < g[node].size(); i++)
        {
            if (!vis[g[node][i].node])
            {
                if (d[g[node][i].node] > d[node] + g[node][i].cost)
                {
                    d[g[node][i].node] = d[node] + g[node][i].cost;
                    addToHeap(g[node][i].node);
                }
            }
        }
    }

    for (int i = 2; i <= n; i++)
        if (d[i] < INF)
            fprintf(out, "%d ", d[i]);
        else
            fprintf(out, "0 ");
    fprintf(out, "\n");

    return 0;
}