#include<fstream>
#include<vector>
#include<set>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

#define pb push_back
#define mp make_pair

const int Nmax = 50003;
const int inf = 1e9;
int n,m,a,b,c,i,d[Nmax];

vector< pair <int,int> > g[Nmax];
set<pair<int,int> > s;

int main()
{
    cin>>n>>m;
    while (m--)
    {
        cin >> a >> b >> c;
        g[a].pb(mp(b,c));
    }
     for (i=2;i<=n;i++)
        d[i] = inf;
     d[1]= 0;

     s.insert(mp(d[1],1));
     while (s.size())
     {
         int nod=s.begin()->second;
         s.erase(s.begin());

         for (i=0;i<g[nod].size();i++)
         {
             int to = g[nod][i].first, len = g[nod][i].second;
             if (d[to] > d[nod] + len)
             {
                 s.erase(mp(d[to],to));
                 d[to] = d[nod] + len;
                 s.insert(mp(d[to],to));
             }
         }
     }
     for (i=2;i<=n;i++)
    if(d[i]==inf) cout<<"0 "; else cout<<d[i]<<' ';
   return 0;
}