#include <fstream>
#include <vector>
#include <queue>
#define inf 1000000005

using namespace std;

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

const int Nmax = 50005;

int n, m, x, y, lg;
int d[Nmax];
bool OK[Nmax];
vector <pair <int, int>> A[Nmax];

struct compara
{
    bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};

priority_queue<int, vector<int>, compara> Q;

void Dijkstra (int start)
{
    for (int i = 2; i <= n; i++)
        d[i] = inf;

    Q.push(start);

    while(!Q.empty())
    {
        int nod = Q.top();
        Q.pop();
        OK[nod] = 0;

        for (auto i = 0; i < A[nod].size(); i++)
        {
            int nod_cur = A[nod][i].first;
            int val_cur = A[nod][i].second;
            int lungime = d[nod] + val_cur;

            if (lungime < d[nod_cur])
            {
                d[nod_cur] = lungime;

                if (OK[nod_cur] == 0)
                {
                    OK[nod_cur] = 1;
                    Q.push(nod_cur);
                }
            }
        }
    }
}

int main()
{
    in >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        in >> x >> y >> lg;
        A[x].push_back(make_pair(y, lg));
    }

    Dijkstra(1);

    for (int i = 2; i <= n; i++)
    {
        if (d[i] == inf)
            out << 0 << ' ';
        else
            out << d[i] << ' ';
    }

    return 0;
}