#include<fstream>
#include<vector>
#include<queue>

#define pii pair <int,int>
#define pinf 999999999
using namespace std;

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

int n,m,i,x,y,c,nod,cost, d[50010];
vector < pii > v[50010];
vector < pii > ::iterator it;
priority_queue < pii, vector<pii > , greater<pii > > q;

int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        d[i]=pinf;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({c,y});
    }
    q.push({0,1});
    while(!q.empty())
    {
        nod=q.top().second;
        cost=q.top().first;
        q.pop();
        if(d[nod]!=pinf)
            break;
        d[nod]=cost;
        for(auto it:v[nod])
            if(d[it.second]==pinf)
                q.push({it.first + cost, it.second});
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<' ';


    fin.close();
    fout.close();
    return 0;
}