#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define INF 1000000001

using namespace std;

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

struct elem
{
    int yy, cost;
    bool operator < (const elem &other) const
    {
        return cost > other.cost;
    }
};

vector <elem> v[50001];
priority_queue <elem> pq;
long long d[50001];
bool viz[50001];
int n, m, xx, yy, cost;

void readit()
{
    in>>n>>m;
    while(m--)
    {
        in>>yy>>xx>>cost;
        v[yy].push_back({xx, cost});
    }
    for(int i=2; i<=n; i++) d[i]=INF;
    pq.push({1, 0});
}

void dig()
{
    while(!pq.empty())
    {
        yy=pq.top().yy;
        cost=pq.top().cost;
        pq.pop();
        if(!viz[yy])
        {
            viz[yy]=1;
            if(d[yy]==INF) d[yy]=cost;
            cost=d[yy];
            for(int i=0; i<v[yy].size(); i++)
                if(!viz[v[yy][i].yy] && d[v[yy][i].yy]>v[yy][i].cost+cost)
                    pq.push({v[yy][i].yy, v[yy][i].cost+cost});
        }
    }
}

int main()
{
    readit();
    dig();
    for(int i=2; i<=n; i++) out<<d[i]<<' ';
    return 0;
}