#include <fstream>
#define INF 1 << 28
#include <vector>
#define dim 50001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
bool viz[dim];
vector < pair <int,int> > G[dim];
int d[dim],a,b,c,i,n,m,poz,Min,j;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    for(i=1;i<=n;i++)
    {
        Min=INF;
        for(j=1;j<=n;j++)
            if(viz[j]==0)
                if(d[j]<Min)
                {
                    Min=d[j];
                    poz=j;
                }
        viz[poz]=1;
        for(j=0;j<G[poz].size();j++)
        {
            if(viz[G[poz][j].first]==0)
                if(d[poz]+G[poz][j].second<d[G[poz][j].first])
                    d[G[poz][j].first]=d[poz]+G[poz][j].second;
        }
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}