#include <fstream>
#include <algorithm>
#include <vector>
#define INF 2000000000

using namespace std;

int N,d[50005];
bool viz[50005];

struct Arc
{
    int y,cost;
};
vector <Arc> L[50005];

inline void Read()
{
    Arc w;
    int i,M,x;
    ifstream fin("dijkstra.in");
    fin>>N>>M;
    for(i=1;i<=M;++i)
    {
        fin>>x>>w.y>>w.cost;
        L[x].push_back(w);
    }
    fin.close();
}

inline void Dijkstra()
{
    int pas,i,nod,j,len,minim;
    for(i=2;i<=N;i++)
        d[i]=INF;
    for(pas=1;pas<=N;pas++)
    {
        minim=INF;
        for(i=1;i<=N;i++)
            if(d[i]<minim && !viz[i])
            {
                minim=d[i];
                nod=i;
            }
        viz[nod]=true;
        len=L[nod].size();
        for(i=0;i<len;i++)
        {
            j=L[nod][i].y;
            d[j]=min(d[j], d[nod]+L[nod][i].cost);
        }
    }
    ofstream fout("dijkstra.out");
    for(i=2;i<=N;i++)
        fout<<d[i]<<" ";
    fout<<"\n";
    fout.close();
}

int main()
{
    Read();
    Dijkstra();
    return 0;
}