#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

vector< pair<int, int> > a[100010];
queue<int> Q;
int n,m,s, viz[100010], d[100010];

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

int main()
{
    f>>n>>m;
    for(int  i = 1; i<=n; ++i)
        d[i] = -1;
    for(int i = 1; i<=m; ++i)
    {
        int x,y,c;
        f>>x>>y>>c;
        a[x].push_back(make_pair(y,c));
    }

     Q.push(1);
     viz[1] = 1;
     d[1] = 0;

     while(!Q.empty())
     {
         int u = Q.front();
         Q.pop();
         viz[u] = 0;

         for(int j =0; j<a[u].size(); ++j)
         {
             int vec = a[u][j].first;
             int cost = a[u][j].second;

             if(d[vec] == -1 || d[vec] > d[u] + cost)
             {
                 d[vec] = d[u]+cost;
                 if(!viz[vec])
                 {
                     viz[vec] = 1;
                     Q.push(vec);
                 }
             }
         }
        //cout<<"lloop\n";
     }

    for(int i =2; i<=n; ++i)
    {
        if(d[i] == -1)
            g<<"0 ";
        else
        g<<d[i]<<" ";
    }
    g<<"\n";

    return 0;
}