#include <bits/stdc++.h>

using namespace std;
int s,d[50001],n,viz[50001],m;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <int>v[250001],l[250001];
void citire()
{fin>>n>>m;
 int x,y,p;
 for(int i=1;i<=m;i++)
 {fin>>x>>y>>p;
  v[x].push_back(y);
  l[x].push_back(p);
 }

}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >h;
void disktra()
{int i;
 for(i=1;i<=n;i++)
    d[i]=(1<<30);
 d[1]=0;
 h.push(make_pair(0,1));
 int nod,w;
 while(!h.empty())
 {nod=h.top().second;
  h.pop();
  if(viz[nod])continue;
  else viz[nod]=1;
  for(i=0;i<v[nod].size();i++)
       {w=v[nod][i];
        if(d[w]>d[nod]+l[nod][i])
            {d[w]=d[nod]+l[nod][i];

             h.push(make_pair(d[w],w));
            }
       }

 }
 for(i=2;i<=n;i++)
    if(d[i]!=(1<<30))fout<<d[i]<<" ";
    else fout<<-1<<" ";
}
int main()
{   citire();
    disktra();;

    return 0;
}