#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
#define pii pair<int,int>
#define mp make_pair

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pii> a[50005];
priority_queue <pii, vector<pii>, greater<pii>> pq;
int n,m,d[50001],t[50001];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin>>z>>x>>y;
        a[z].push_back(mp(y,x));
    }
    d[1]=0;
   pq.push(mp(0,1));
   while(!pq.empty())
   {
       int nod=pq.top().second;
       for(int i=0; i<a[nod].size();i++)
       {
           if(d[a[nod][i].second]>d[nod]+a[nod][i].first)
           {
               d[a[nod][i].second]=d[nod]+a[nod][i].first;
               t[a[nod][i].second]=nod;
               pq.push(mp(d[a[nod][i].second],a[nod][i].second));
           }

       }
       pq.pop();
   }
   for(int i=2;i<=n;i++)
    {
        fout<<d[i]<<" ";
    }
    return 0;
}