#include <fstream>
#include <bits/stdc++.h>
#define nmax 50001

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m;
vector<pair<int,int>> v[nmax];
set<pair<int,int>> s;
int viz[nmax];
int d[nmax];

void read()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
            int x,y,z;
            fin>>x>>y>>z;
            v[x].push_back(make_pair(y,z));
        }
    for(i=1; i<=n; i++)
         d[i]=1e9;
}

void dijkstra()
{
    unsigned int i;
    s.insert(make_pair(0,1));
    while(!s.empty())
         {
             int dist=s.begin()->first;
             int nod=s.begin()->second;
             s.erase(s.begin());
             for(i=0; i<v[nod].size(); i++)
                {
                    int nod_urm=v[nod][i].first;
                    int dist2=v[nod][i].second;
                    if(viz[nod_urm]==0)
                       { //fout<<"DA";
                           if(dist2+dist<=d[nod_urm])
                              {
                                  if(d[nod_urm]!=1e9) s.erase(s.find(make_pair(d[nod_urm],nod_urm)));
                                  d[nod_urm]=dist2+dist;
                                  s.insert(make_pair(d[nod_urm],nod_urm));
                              }
                       }
                }
            viz[nod]=1;
         }
}

int main()
{
    read();
    dijkstra();
    int i;
    for(i=2; i<=n; i++)
        if(d[i]==1e9) fout<<0<<" ";
        else fout<<d[i]<<" ";
    return 0;
}