#include <fstream>
#include <vector>
#define N 50002
#define INF 2000000000

using namespace std;

struct bla
{
    int ve, co;
};
vector <bla> graph[N];
int dist[N], heap[N], cate, poz[N];


void up(int nod, int i)
{
    while (i > 1 && dist[heap[i / 2]] > dist[heap[i]])
    {
        swap(poz[heap[i / 2]], poz[heap[i]]);
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}
void down(int nod, int i)
{
    int pozfiu;
    do
    {
        pozfiu = 0;
        if (2 * i <= cate)
        {
            pozfiu = 2 * i;
            if (2 * i + 1 <= cate && dist[heap[2 * i + 1]] < dist[heap[2 * i]])
                pozfiu = 2 * i + 1;
        }
        if (pozfiu && dist[heap[pozfiu]] < dist[nod])
        {
            swap(poz[heap[pozfiu]], poz[nod]);
            swap(heap[pozfiu], heap[i]);
            i = pozfiu;
        }
        else
            pozfiu = 0;
    } while (pozfiu);
}
void dijkstra()
{
    int nod, father;
    heap[++cate] = 1;
    poz[1] = 1;///nod se afla pe pozitia poz[nod] in heap
    while (cate)
    {
        nod = heap[1];
        heap[1] = heap[cate--];
        poz[heap[1]] = 1;
        down(heap[1], 1);
        for (int i = 0;i < graph[nod].size();++i)
        {
            if (dist[nod] + graph[nod][i].co < dist[graph[nod][i].ve])
            {
                dist[graph[nod][i].ve] = dist[nod] + graph[nod][i].co;
                if (poz[graph[nod][i].ve])///se afla deja in heap
                    up(graph[nod][i].ve, poz[graph[nod][i].ve]);
                else
                {
                    heap[++cate] = graph[nod][i].ve;
                    poz[graph[nod][i].ve] = cate;
                    up(heap[cate], cate);
                }
            }
        }
    }
}
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, m, x, y, c;
    f >> n >> m;
    for (int i = 1;i <= m;++i)
    {
        f >> x >> y >> c;
        graph[x].push_back({ y,c });
    }
    for (int i = 2;i <= n;++i) dist[i] = INF;
    dijkstra();
    for (int i = 2;i <= n;++i)
        if (dist[i] == INF)
            g << 0 << ' ';
        else
            g << dist[i] << ' ';
    f.close();
    g.close();
    return 0;
}