#include <bits/stdc++.h>

using namespace std;

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

struct el
{
    int node, cost;
    bool operator < (const el &A) const{
        return cost > A.cost;
    }
};

int n, m;
int dmin[50005];
bool visited[50005];

vector < el > L[50005];

priority_queue < el > Q;

void read()
{
    fin >> n >> m;
    int x;
    el w;
    for(int i = 1; i <= m; i ++)
    {
        fin >> x;
        fin >> w.node >> w.cost;
        L[x].push_back(w);
    }
}

void dijkstra()
{
    for(int i = 2; i <= n; i ++)
        dmin[i] = 1e9;

    el w, w2;
    int cost, node2;

    w.node = 1;
    w.cost = 0;
    Q.push(w);
    while(!Q.empty())
    {
        el p = Q.top();
        Q.pop();

        for(auto it : L[p.node])
        {
            node2 = it.node;
            cost = it.cost + dmin[p.node];

            if(dmin[node2] > cost)
            {
                dmin[node2] = cost;
                w2.node = node2;
                w2.cost = dmin[p.node];
                Q.push(w2);
            }
        }
    }
}

void write()
{
    for(int i = 2; i <= n; i ++)
    {
        if(dmin[i] != 1e9)
            fout << dmin[i] << ' ';
        else fout << 0 << " ";
    }
}

int main()
{
    read();
    dijkstra();
    write();
    return 0;
}