#include <fstream>
#include <vector>
#include <queue>
#define oo 0x3f3f3f3f

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

typedef  pair <int, int> PER;
vector <PER> G[50001];
int D[50001],P[50001];
bool V[50001];

int main()
{
    int N,m;
    fin>>N>>m;
    for(int i=1;i<=m;++i){
        int x,y,z;
        fin>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
    }
    for(int i=0;i<=N;i++)
        {D[i]=oo;P[i]=0;V[i]=false;}
    V[1]=true;D[1]=0;
    queue<int>Q; Q.push(1);
    while(!Q.empty()){
    int nod=Q.front();
    V[nod]=false;
    vector<PER>::iterator i;//am definit cu typedef PER ...
    for(i=G[nod].begin();i!=G[nod].end();++i)
    if (D[nod]+i->second<D[i->first])
    {D[i->first]=D[nod]+i->second;
    P[i->first]=nod;
    if(!V[i->first])
    {Q.push(i->first);
    V[i->first]=true;}
    }
    Q.pop();
    }
    for(int i=2;i<=N;i++)
        fout<<D[i]<<" ";
    return 0;
}