#include <fstream>
#include <vector>
#include <queue>
#define N 50005
#define INF 10000000
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

priority_queue < pair <int,int>, vector<pair <int,int>  >, greater<pair <int,int> >  > Q;
vector <pair <int,int> > g[N];
void djk(int s);
int n;
int v[N],dist[N],uz[N];
int main()
{
    int t,m,s,i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        {
            fin>>x>>y>>c;
            g[x].push_back({c,y});
        }
    djk(1);
    for(i=2;i<=n;i++)
            if(dist[i]==INF) fout<<0<<" ";
            else fout<<dist[i]<<" ";
    return 0;
}

void djk(int s)
{
    int i,nod,cost;
    for(i=1;i<=n;i++)
        dist[i]=INF;
    dist[s]=0;
    for(i=0;i<g[s].size();i++)
        {
            dist[g[s][i].second]=g[s][i].first;
            Q.push(g[s][i]);
        }
    uz[s]=1;
    while(!Q.empty())
    {
        nod=Q.top().second;
        cost=Q.top().first;
        uz[nod]=1;
        Q.pop();
        for(i=0;i<g[nod].size();i++)
            if(!uz[g[nod][i].second])
                if(dist[g[nod][i].second]> dist[nod]+ g[nod][i].first)
                {
                    dist[g[nod][i].second]=dist[nod]+ g[nod][i].first;
                    Q.push({g[nod][i].second,dist[g[nod][i].second]});
                }
    }

}