#include <iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<queue>
#define INF 1000000001
#define NMAX 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int N, M;
vector < pair<int, int> >G[NMAX];
int dmin[NMAX], prec[NMAX];
class comparvf
{
public:
    bool operator()(const int&x, const int& y)
    {
        return dmin[x] > dmin[y];
    }
};
priority_queue<int, vector<int>,comparvf>H;

void citire()
{int x,y,c;
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}
void dijkstra()
{
    int vfmin;
    for(int i=1;i<=N;i++)
    {
        dmin[i]=INF;
        prec[i]=1;
    }
    dmin[1]=0;
    prec[1]=0;
    H.push(1);
    while(!H.empty())
    {
        vfmin=H.top();
        H.pop();
        for(unsigned int i=0;i<G[vfmin].size();i++)
            if(dmin[G[vfmin][i].first]>dmin[vfmin]+G[vfmin][i].second)
        {
            dmin[G[vfmin][i].first]=dmin[vfmin]+G[vfmin][i].second;
            prec[G[vfmin][i].first]=vfmin;
            H.push(G[vfmin][i].first);
        }
    }
}
void afisare()
{
    for(int i=2;i<=N;i++)
    {
        if(dmin[i]==INF)
            g<<0<<' ';
        else
            g<<dmin[i]<<' ';
    }
}
int main()
{citire();
dijkstra();
afisare();
    return 0;
}