#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
int n,m;
struct edge
{
    int nod,cost;
};

void citire(vector<vector<edge>>&G)
{
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    G = vector<vector<edge>> (n + 1);
    for(int i=1;i<=m;i++)
    {
        int a,b,cost;
        fin>>a>>b>>cost;
        edge muchie;
        muchie.nod=b,muchie.cost=cost;
        G[a].push_back(muchie);
    }
    fin.close();
}
void dijkstra(vector<vector<edge>>G)
{
    ofstream fout("dijkstra.out");
    int inf=(n-1)*20000;
    vector<int> d(n+1,inf);
    vector<int> viz(n+1,0);
    d[1]=0;
    int i,j,ind=-1;
    for(i=1;i<=n;i++)
    {
        int minim=inf;
        for(j=1;j<=n;j++)
     {
        if(d[j]<minim && !viz[j])
        {
            minim=d[j];
            ind=j;
        }
     }
     if(ind==-1) break;
     viz[ind]=1;
        for(auto edge:G[ind])
        {
            if(d[edge.nod]>d[ind]+edge.cost)
                d[edge.nod]=d[ind]+edge.cost;
        }
    }
    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";
    fout.close();
}
int main()
{
    vector<vector<edge>>G;
    citire(G);
    dijkstra(G);
    return 0;
}