#include <bits/stdc++.h>

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
#define INF 0x3f3f3f3f

int n,m,x,y,p,d[100001],w;
vector<pair<int,int>>a[100001];
void dijkstra(int nod)
     {
         priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
         d[nod]=0;
         q.push({0,nod});
         while(!q.empty())
         {
             x=q.top().first;
             y=q.top().second;
             q.pop();
             if (x>d[y])
                 continue;
             for (auto &u:a[y])
             {
                 int nodnou=u.first;
                 int costnou=u.second;
                 if (d[nodnou]>d[y]+costnou)
                 {
                     d[nodnou]=d[y]+costnou;
                     q.push({d[nodnou],nodnou});
                 }
             }
         }
     }
int main()
{
    f>>n>>m;
    for (;m;m--)
        {
        f>>x>>y>>w;
        a[x].push_back({y,w});
        }
    for (int i=1;i<=n;i++)
         d[i]=INF;
    dijkstra(1);
    for (int i=2;i<=n;i++)
         if (d[i]==INF)
             g<<"-1"<<" ";
         else
             g<<d[i]<<" ";
    return 0;
}