#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int INF = 1e9;
const int NMAX = 50001;
int N, M;

///listele de adiacenta (first-ul contine nodul vecin, second-ul contine costul muchiei)
vector < pair <int, int> > a[NMAX]; 

/// contine nodurile carora li s-a imbunatatit 
/// costul drumului(first-ul din pair contine costul, iar second-ul contine nodul vecin)
priority_queue < pair <int, int> > pq;

int d[NMAX]; /// d[i] reprezinta drumul curent de la start la i
bool vizitat[NMAX];

void dijkstra(int start)
{
    for (int i = 1; i <= N; ++i)
        d[i] = INF;

    d[start] = 0;
    pq.push({-d[start], start});

    while (!pq.empty())
    {
        int minim = pq.top().second;
        pq.pop();
        
        if (!vizitat[minim])
        {
            vizitat[minim] = true;
            for (auto vecin: a[minim])
            {
                int val_vecin = vecin.first;
                int cost_vecin = vecin.second;
                if (d[val_vecin] > d[minim] + cost_vecin)
                {
                    d[val_vecin] = d[minim] + cost_vecin;
                    pq.push({-d[val_vecin], val_vecin});
                }
            }
        }
    }
}

int main()
{

    in >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, c;
        in >> x >> y >> c;
        a[x].push_back({y, c});
    }

    dijkstra(1);

    for (int i = 2; i <= N; ++i)
    {
        if (d[i] == INF)
            d[i] = 0;
        
        out << d[i] << ' ';
    }
    return 0;
}