#include<fstream>
#include<vector>
#define numaru 50001
#define INF (1<<23)
#define INFILE "dijkstra.in"
#define OUTFILE "dijkstra.out"
using namespace std;
vector < pair<int, int> > Graf[numaru];
int n,d[numaru];
bool marc[numaru];
void citire()
{
    ifstream f(INFILE);
    int m,i,j,c;
    f>>n>>m;
    for(;m;--m)
    {
        f>>i>>j>>c;
        Graf[i].push_back(make_pair(j,c));
    }
    f.close();
}

void scrierez()
{
    ofstream g(OUTFILE);
    for(int i=2;i<=n;++i) g<<d[i]<<" ";
    g.close();
}

void dijkstra_in_action()
{
    int _min,poz,marcate,i;
    for(i=1;i<=n;++i) d[i]=INF;
    for(i=0;i<Graf[1].size();++i) d[Graf[1][i].first]=Graf[1][i].second;
    d[1]=0;
    marc[1]=true;
    while(marcate!=n)
    {
        _min=INF;
        for(i=1;i<=n;++i)
            if(marc[i]==false && _min>d[i]) _min=d[i],poz=i;
        if(_min==INF)break;
        marc[poz]=true;
        ++marcate;
        for(i=0;i<Graf[poz].size();++i)
            if(d[Graf[poz][i].first]>d[poz]+Graf[poz][i].second)
                d[Graf[poz][i].first]=d[poz]+Graf[poz][i].second;
    }
}

int main()
{
    citire();
    dijkstra_in_action();
    scrierez();
    return 0;
}