//DIJKSTRA CU PARSARE
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream is ("dijkstra.in");
ofstream os ("dijkstra.out");

#define PII pair<int,int>

const int INF = 0x3f3f3f3f;

int N, M;
int Cost[50001];
bool Relaxed[50001];

vector <PII> Graph[50001];
priority_queue <PII, vector <PII>, greater<PII> > Q;        // cost, nod

char Pars[1<<17], *p;

void Check();
int GET();
void Read();

void Dijkstra();

int main()
{

    Read();
    Dijkstra();


    is.close();
    os.close();

}

#define j next.first
#define c next.second

void Dijkstra()
{
    for (int i = 1; i <= N; ++i)
        Cost[i] = INF;

    Cost[1] = 0;
    Q.push({0, 1});

    for (int i; !Q.empty();)
    {

        i = Q.top().second;
        Relaxed[i] = 1;

        for (const auto& next : Graph[i])
            if (Cost[j] > Cost[i] + c)
                Cost[j] = Cost[i] + c,
                Q.push({Cost[j], j});

        while (!Q.empty() && Relaxed[Q.top().second] == 1)
            Q.pop();

    }

    for (int i = 2; i <= N; ++i)
        os << Cost[i] << ' ';
};

void Read()
{
    p = Pars;
    Check();

    N = GET();
    M = GET();

    for (int A, B, C; M; --M)
    {
        A = GET();
        B = GET();
        C = GET();

        Graph[A].push_back({B, C});
        Graph[B].push_back({A, C});
    }
};

void Check()
{
    if (*p == '\0')
        is.get(Pars, 1<<17, '\0'), p = Pars;
};

int GET()
{
    while (*p < '0' || '9' < *p) ++p, Check();
    int X = 0;

    while ('0' <= *p && *p <= '9') X = X*10 + (*p - '0'), ++p, Check();
    return X;
};