// infoarena: problema/dijkstra (rewrite) //

#include <fstream>
#include <queue>
#include <vector>
#define MAXN 50010
#define MAXM 250010
#define INF (1<<30)
using namespace std;

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

int n,m,i,j,dist[MAXM],fin[MAXM],res[MAXN],a,b,c,next,k[MAXN];
bool viz[MAXN];

struct cmp
{
    bool operator() (int a, int b) const
    {
        return k[a] > k[b];
    }
};

priority_queue<int, vector<int>, cmp > q;
vector<int> g[MAXN];
vector<int>::iterator it;

int main()
{
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>a>>b>>c;
        g[a].push_back(i);
        fin[i] = b;
        dist[i] = c;
    }

    for(i=2; i<=n; i++)
        res[i] = INF;

    q.push(1);

    int num = n-1;
    while(!q.empty())
    {
        do
        {
            next = q.top();
            q.pop();
        } while(!q.empty() && res[next!=INF]);

        if(q.empty() && res[next] == INF)
            break;

        res[next] = k[next];

        for(it = g[next].begin(); it != g[next].end(); ++it)
            if(res[fin[*it]] == INF)
            {
                k[fin[*it]] = res[next] + dist[*it];
                q.push(fin[*it]);
                --num;
            }
    }

    for(i=2; i<=n; i++)
        out<<res[i]<<' ';

    return 0;
}