#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
unsigned int n,m, d[inf];
vector < pair <int, int> > v[inf];
priority_queue < pair<int,int> > q;

void citire()
{
    int i,j,k,c;
    f>>n>>m;

    for(k=1; k<=m; k++)
    {
       f>>i>>j>>c;
       v[i].push_back({j,c});
    }
}

void dijkstra(int start)
{
    int i,mn,poz,k, nod, cost;

    for(i=2; i<=n; i++)
            d[i]=inf;

    q.push({0, start });
    while(!q.empty())
    {
        poz=q.top().second;
        q.pop();

        for(i=0; i<v[poz].size(); i++)
        {
            cost=v[poz][i].second;
            nod=v[poz][i].first;
                if(d[nod]>d[poz]+cost)
            {
                d[nod]=d[poz]+cost;
                q.push({ -d[nod], nod });
            }
        }
    }
}

int main()
{
    citire();
    dijkstra(1);
    for(int i=2; i<=n; i++)
        if(d[i]==inf)
        g<<0<<" ";
        else
        g<<d[i]<<" ";
    f.close();
    g.close();
    return 0;
}