#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <utility>
#define NMAX 100000

using namespace std;

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

struct cmp
{
    bool operator () (pair <int,int>a,pair <int,int> b)
{
    return a.second<b.second;
}
};
int n,m;
vector <pair <int,int>> v[NMAX];
vector <int> viz,res;
set <pair <int,int>,cmp> q;

void afis()
{
    for(auto x:q)
        cout<<x.first<<' '<<x.second<<" ; ";
    cout<<'\n';
}

void djikstra()
{
    int i=0;
    viz[0]=1;
    for(auto x:v[0])
        {
            q.insert(make_pair(x.first,x.second));
        }
    while(!q.empty())
    {
        pair <int,int> p=*q.begin();
        q.erase(p);
        if(viz[p.first])
            continue;
        res[p.first]=p.second;
        viz[p.first]=1;
        for(auto x:v[p.first])
        {
            if(!viz[x.first] && (!res[x.first] || p.second+x.second<res[x.first]))
            {
                q.insert(make_pair(x.first,p.second+x.second));

            }
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=0;i<n;++i)
    {
        viz.push_back(0);
        res.push_back(0);
    }
    while(m--)
    {
        int x,y,z;
        f>>x>>y>>z;;
        v[x-1].push_back(make_pair(y-1,z));
    }
    djikstra();
    for(auto x:res)
        g<<x<<' ';
    return 0;
}