#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int Max=50005;
vector< pair<int ,int> >v[Max];
int n,m,D[Max];
bool marca[Max];
struct compara
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};
priority_queue< int, vector<int>, compara > q;
void citire(){
f>>n>>m;int x,y,z;
for(int i=1;i<=m;i++){
    f>>x>>y>>z;
v[x].push_back(make_pair(y,z));
}
}
void Dijkstra()
{
    int nod,ve,co;
    q.push(1);
    while(!q.empty())
    {
        nod=q.top();
        q.pop();
        for(int i=0;i<v[nod].size();i++)
        {ve=v[nod][i].first;
        co=v[nod][i].second;
        if((D[ve]>D[nod]+co)||(D[ve]==0)){
            D[ve]=D[nod]+co;
                q.push(ve);


        }

        }
    }
}
void afisare(){
for(int i=2;i<=n;i++)g<<D[i]<<" ";

}




int main()
{
citire();
Dijkstra();
afisare();
}