#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define max_size 20000005
int x,y,z,N,M;
int dis[50005],viz[50005];
vector < pair <int,int> > graph[50005];
void dijkstra(int x)
{
    for(int i=1;i<=N;i++)
        dis[i]=max_size;
    dis[x]=0;
    for(int j=0;j<N;j++)
    {
       int min=max_size;
    int index=-1;
    for(int i=1;i<=N;i++)
    {
        if(!viz[i] && dis[i]<min)
        {
            min=dis[i];
            index=i;
        }
    }
        viz[index]=1;
        int lim=graph[index].size();
        for(int i=0;i<lim;i++)
        {
            int vecin=graph[index][i].first;
            if(dis[vecin]>dis[index]+graph[index][i].second)
                dis[vecin]=dis[index]+graph[index][i].second;
        }
    }

}
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>N>>M;
    for(int i=0;i<M;i++)
    {
        fin>>x>>y>>z;
        graph[x].push_back(make_pair(y,z));
    }
    dijkstra(1);
    for(int i=2;i<=N;i++)
    {
        if(dis[i]==max_size) dis[i]=0;
        fout<<dis[i]<<" ";
    }
    return 0;
}