#include<fstream>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct pereche{int n,c;};
vector <pereche> a[50001];
int d[50001];
bitset<50001> apar;

void dijkstra(int nod)
{
     int i , curent;
     queue<int> q;
     q.push(nod);
     apar[nod]=1;
     while(!q.empty())
     {
                      nod=q.front();
                      q.pop();
                      apar[nod]=0;
                      for(i=0; i<a[nod].size();i++)
                      {
                               curent=a[nod][i].n;
                               if(d[curent]==0 || d[curent]>d[nod]+a[nod][i].c)
                               {
                                               d[curent]=d[nod]+a[nod][i].c;
                                               if(apar[curent]==0)
                                               {
                                                                  q.push(curent);
                                                                  apar[curent]=1;
                                                                  
                                               }
                               }
                      }
                      
     }
     
}

int main()
{
    int n , m;
    f>>n>>m;
    int i , q;
    pereche z;
    for(i=1; i<=m; i++)
    {
             f>>q>>z.n>>z.c;
             a[q].push_back(z);
    }
    dijkstra(1);
    for(i=2; i<=n; i++) g<<d[i]<<" ";
}