#include <fstream>
#include <vector>
#include <queue>
#define inf 1e9
using namespace std; 
ifstream f ("dijkstra.in") ;
ofstream g ("dijkstra.out") ;
int N , M , x ,y;
bool viz[50010] ;
int cost , d[50010]; 
vector <pair<int,int> > v[50010] ;
priority_queue <pair <int,int> , vector <pair<int,int> > , greater <pair<int,int> > > h; 
void Dijkstra()
{
    h.push({0,1});
    while (!h.empty())
    {
        int nod = h.top().second;
        h.pop(); 
        int lg = v[nod].size() ;
        if (!viz[nod])
        for (int i = 0 ; i < lg ; ++i)
        {
            int vec = v[nod][i].second ;
            if (d[vec] > d[nod] + v[nod][i].first)
            {
                d[vec] = d[nod] + v[nod][i].first;
                h.push({d[vec],vec}) ;
            }
            
        }
        
        viz[nod] = true; 
    }
}
int main()
{
    f >> N >> M ;
    for (int i = 1 ; i <= M ; ++i)
    {
        f >> x >> y >> cost; 
        v[x].push_back({cost,y});
    }
    
    d[1] = 0 ;
    for (int i = 2 ; i <= N ; ++i) d[i] = inf ;
    
    Dijkstra() ;
    
    for (int i = 2 ;  i<= N ; ++i)
    if (d[i] == inf) g << 0 << ' ';
    else g << d[i] << ' ' ;
    
}