#include <fstream>
#include <vector>
using namespace std;
string file = "dijkstra";
ifstream cin(file +".in");
ofstream cout(file +".out");
const int N = 100001, INF = 1<<30;

struct muchie{
    int nod,cost;
};


int h[N], nh, n, poz[N];
vector <muchie> L[N];
vector <int> d;

void schimb(int p1, int p2)
{
    swap(h[p1], h[p2]);
    poz[h[p1]] = p1;
    poz[h[p2]] = p2;
}

void urca(int p)
{
    while (p>1 && d[h[p/2]] > d[h[p]])
    {
        schimb(p/2,p);
        p/=2;
    }
}

void coboara(int p)
{

    while (true)
    {
        int bun = p, fs = p*2, fd=p*2+1;
        if (fs <= nh && d[h[bun]] > d[h[fs]])
        {
            bun = fs;
        }
        if (fd <= nh && d[h[bun]] > d[h[fd]])
        {
            bun = fd;
        }
        if (bun == p)
        {
            break;
        }
        schimb(bun,p);
        p = bun;
    }
}

void adauga(int nod)
{
    h[++nh] = nod;
    poz[nod] = nh;
    urca(nh);
}
void sterge(int p)
{
    schimb(p,nh);
    nh--;
    urca(p);
    coboara(p);
}
void bfs(int x)
{
    d[x] = 0;
    adauga(x);
    while (nh)
    {
        x = h[1];
        sterge(1);
        for (auto y : L[x])
        {
            if (d[x] + y.cost < d[y.nod])
            {
                d[y.nod] = d[x] + y.cost;
                if (poz[y.nod] == 0)
                {
                    adauga(y.nod);

                }
                else
                {
                    urca(poz[y.nod]);
                }
            }
        }
    }
}
int main()
{
    int n, m, x,y,z;
    cin >> n >> m;
    while (m)
    {
        cin >> x >> y >> z;
        L[x].push_back({y,z});
        m--;
    }
    d.resize(n+1,INF);
    bfs(1);
    for (int i=2; i<=n; i++)
    {
        if (d[i] == INF)
            d[i] = 0;
        cout << d[i] << ' ';
    }
}