#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n,m;
priority_queue < pair <int,int> > pq;
vector < pair <int,int> > v[50001];
pair <int,int> p;
int ans[50001];
bool ok[50001];

void dijkstra()
{
    pq.push({0,1});
    while (!pq.empty())
    {
        p=pq.top();
        pq.pop();
        swap(p.first,p.second);
        p.second*=-1;
        if (ans[p.first]<p.second&&ok[p.first]) //s-a gasit deja o solutie mai buna pt nodul curent deci sarim peste el
            continue;
        int nod,dist;
        for (int i=0;i<v[p.first].size();i++)
        {
            nod=v[p.first][i].second;
            dist=v[p.first][i].first;
            if (ok[nod]&&ans[nod]<=p.second+dist) //s-a gasit un drum mai optim pt unul din vecini
                continue;
            pq.push({-dist-p.second,nod});
            ok[nod]=1;
            ans[nod]=dist+p.second;
        }
    }
}

int main()
{
    int a,b,k,x;
    in>>n>>m;
    for (int i=1;i<=m;i++)
        in>>a>>b>>k,v[a].push_back({k,b});
    dijkstra();
    for (int i=2;i<=n;i++)
        out<<ans[i]<<" ";
    return 0;
}