#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
//typedef pair<int,int> pii;
const int inf=1e9;
using namespace std;
ifstream fin("dijkstra.in",ios::in);
    ofstream fout("dijkstra.out",ios::out);
bool viz[50001];
int dist[50001];
int N,i,M,x,y,cost,j;
vector <pair <int,int> > v[50001];
//priority_queue <int,vector<int>,compare> C ;
/*bool comparare(const int i,const int j)
{
    return (dist[i]>dist[j]);
}*/
typedef struct
{
    inline bool operator ()(const int i ,const int j)
    {
        return (dist[i]>dist[j]);
    }
}compare;
priority_queue <int,vector<int>,compare> C ;
int main()
{
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    dist[1]=0;
    for(i=2;i<=N;i++)
    {
        dist[i]=inf;
    }
    C.push(1);
    while (!C.empty())
    {
        x=C.top();
        viz[x]=0;
        C.pop();

        for(i=0;i<v[x].size();i++)
        {
            y=v[x][i].first;
            cost=v[x][i].second;
            if(dist[y]>dist[x]+cost)
            {
                dist[y]=dist[x]+cost;
                if (viz[y]==false)
                {
                    viz[y]=true;
                    C.push(y);
                }
            }
        }
    }
    for(i=1;i<=N;i++)
    {
        if(dist[i]==inf)
        {
            dist[i]=0;
        }
    }
    for(i=2;i<=N;i++)
    {
        fout<<dist[i]<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}