#include <fstream>
#include <vector>
#define DIM 50002
#define a first
#define b second
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector < pair <int ,int > > v[DIM];
int n,m,p,u,C[DIM],dist[DIM];
bool viz[DIM];
int main(){
    fin>>n>>m;
    while(m--){
        int x,y,D;
        fin>>x>>y>>D;
        v[x].push_back(make_pair(y,D));
    }
    p=u=1;
    C[1]=1;
    viz[1]=1;
    while(p<=u){
        int x=C[p++];
        for(int i=0;i<v[x].size();i++)
            if(!viz[v[x][i].a]){
                viz[v[x][i].a]=1;
                dist[v[x][i].a]=dist[x]+v[x][i].b;
                C[++u]=v[x][i].a;
            }
    }
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<" ";
    fin.close();fout.close();
    return 0;
}