#include <fstream>
#include <vector>
#include <set>
#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()
{
    fin>>n>>m;
    int i,x,y,z;
    for(i=1; i<=m; i++)
       {
           fin>>x>>y>>z;
           v[x].push_back(make_pair(y,z));
       }
    for(i=1; i<=n; i++) d[i]=1e9;
    d[1]=0;
}

void dijkstra()
{
    int i,j;
    s.insert({0,1});
    while(!s.empty())
        {
            int dist=s.begin()->first;
            int nod=s.begin()->second;
            int ct=v[nod].size();
            s.erase(s.begin());
            for(int i=0; i<ct; i++)
               {
                   int dist2=v[nod][i].second;
                   int nod_vec=v[nod][i].first;
                   if(!viz[nod_vec])
                      {
                          if(d[nod_vec]>dist+dist2)
                             {
                                 s.erase(make_pair(d[nod_vec],nod_vec));
                                 d[nod_vec]=dist+dist2;
                                 s.insert(make_pair(d[nod_vec],nod_vec));

                             }
                      }
               }
            viz[nod]=1;
        }

}

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