#include <cstdio>
#include <vector>

using namespace std;

struct edge
{
    int node;
    int cost;
};

vector<edge> g[50001];
bool vis[50001];
int dist[50001];
int next_node[100001];
int heap[100001];
int heap_length = 0;

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

void add(int cost, int node)
{
    int i = ++heap_length;
    heap[i] = cost;
    next_node[i] = node;
    while (heap[i] < heap[i/2])
    {
        swapValues(i, i/2);
        i /= 2;
        if (i == 1)
            break;
    }
}

// delete from heap
void del()
{
    heap[1] = heap[heap_length];
    next_node[1] = next_node[heap_length];
    --heap_length;
    int i = 1;
    int vmin;
    bool ok = false;
    while (!ok)
    {
        vmin = i;
        if (2*i <= heap_length && heap[2*i] < heap[vmin])
            vmin = 2*i;
        if (2*i+1 <= heap_length && heap[2*i+1] < heap[vmin])
            vmin = 2*i+1;
        if (vmin != i)
        {
            swapValues(i, vmin);
            i = vmin;
        }
        else
            ok = true;
    }
}

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

    int n, m;
    fscanf(in, "%d%d", &n, &m);
    for (int x, y, c; m >= 0; --m)
    {
        fscanf(in, "%d%d%d", &x, &y, &c);
        edge t;
        t.node = y;
        t.cost = c;
        g[x].push_back(t);
    }

    add(0, 1);
    int node, cost;
    while (heap_length)
    {
        node = next_node[1];
        cost = heap[1];
        del();
        if (vis[node])
            continue;
        vis[node] = 1;
        dist[node] = cost;
        for (int i = 0; i < g[node].size(); ++i)
            if (!vis[g[node][i].node])
                add(cost + g[node][i].cost, g[node][i].node);
    }

    fprintf(out, "%d", dist[2]);
    for (int i = 3; i <= n; ++i)
        fprintf(out, " %d", dist[i]);
    fprintf(out, "\n");

    return 0;
}