#include <cstdio>
#include <iostream>
#include <vector>
#include <bitset>
#include <set>
#include <cstring>
using namespace std;

#define MAXN 50050
#define INF 0x3f3f3f3f

FILE* fin = fopen ("dijkstra.in", "rb");
FILE* fout = fopen ("dijkstra.out", "w");

const int bufSize = 8192;
char buf[bufSize];
int ptr = bufSize - 1;

inline int getInt ()
{
    while (buf[ptr] < '0' || '9' < buf[ptr])
    {
        if (++ptr >= bufSize)
        {
            fread (buf, bufSize, 1, fin), ptr = 0;
        }
    }
    int nr = 0;
    while ('0' <= buf[ptr] && buf[ptr] <= '9')
    {
        nr = nr * 10 + buf[ptr] - '0';
        if (++ptr >= bufSize)
        {
            fread (buf, bufSize, 1, fin), ptr = 0;
        }
    }
    return nr;
}

typedef vector<pair<int,int> >::iterator iter;
typedef set<pair<int, int> >::iterator siter;

int n, m, d[MAXN];
vector<pair<int,int> > g[MAXN];
set<pair<int, int> > s;
bitset<MAXN> viz;

void dijkstra()
{
    memset(d, 0x3f, sizeof(d));

    d[1] = 0;
    s.insert(make_pair(0, 1));

    while (!s.empty()) {
        int top = s.begin()->second;
        viz[top] = true;
        s.erase(s.begin());

        for(iter it=g[top].begin(); it!=g[top].end(); it++)
        {
            if(!viz[it->first] && (d[it->first] > d[top] + it->second))
            {
                siter st = s.find(make_pair(d[it->first], it->first));
                if (st != s.end()) {
                    s.erase(st);
                }

                d[it->first] = d[top] + it->second;
                s.insert(make_pair(d[it->first], it->first));
            }
        }
    }
}

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

    n = getInt(), m = getInt();

    for(int i = 0; i < m; i++)
    {
        int x = getInt(), y = getInt(), c = getInt();
        g[x].push_back(make_pair(y, c));
    }

    dijkstra();

    for(int i = 2; i <= n; i++)
    {
        fprintf(fout, "%d ",(d[i] == INF) ? 0 : d[i]);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}