#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<queue>
#include <utility>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define inf 10000000

struct nod
{
    int y;
    int cost;
};
vector <nod> G[50001];
priority_queue< pair <int,int> > q;
pair <int,int> aux;
int n,m,a,b,c,i;
int rez[50001];
int viz[50001];

int main()
{    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        G[a].push_back({b,c});
    }
    for(i=1;i<=n;++i)
        rez[i]=inf;
    rez[1]=0;
    viz[1]=1;
    q.push({0,1});
    while(!q.empty())
    {
        aux=q.top();
        q.pop();
        if(viz[aux.first]==0)
           {
               for(auto p:G[aux.second])
               {
                   if(rez[p.y]>p.cost+rez[aux.second])
                        rez[p.y]=p.cost+rez[aux.second];
                   q.push({-rez[p.y],p.y});
               }
               viz[aux.first]=1;
            }
    }
    for(i=2;i<=n;i++)
        g<<rez[i]<<" ";
    f.close();
    g.close();
    return 0;
}