#include <fstream>
#include <set>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int noduri,muchii;

struct mc{
long long nod;
long long cost;
bool operator <(const mc& a) const {return cost<a.cost;};

};

vector <mc> v[50001];

long long d[50001];
bool viz[50001];

set <mc> msort;

int main()
{
    fin>>noduri>>muchii;
    for(int i=2;i<=noduri;i++)
    {
        d[i]=LLONG_MAX;
    }

    for(int i=1;i<=muchii;i++)
    {
        int x,y,c;
       fin>>x>>y>>c;
       v[x].push_back({y,c});
    }
    msort.insert({1,0});
    while(!msort.empty())
    {
        long long nodd = msort.begin()->nod;
        msort.erase(msort.begin());

        for(int i=0;i<v[nodd].size();i++)
        {
            long long vecin = v[nodd][i].nod;
            long long cost = v[nodd][i].cost;
            if(d[nodd]+cost<d[vecin])
            {
                msort.erase({vecin,d[vecin]});
                d[vecin]=d[nodd]+cost;
                msort.insert({vecin,d[vecin]});
            }
        }
    }
    for(int i=2;i<=noduri;i++)
    {
        fout<<d[i]<<' ';
    }

}