#include <fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include <cmath>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int oo=1<<30;
int n,m,tot,D[50001];
struct compara{
    bool operator()(int x,int y)
    {
        return D[x]>D[y];
    }
};
int main()
{
        f>>n>>m;
priority_queue<int, vector<int>, compara> Coada;
        int sol[n+1];
        for(int i=1;i<=n;++i)
            D[i]=oo;
        int x,y,c;
        bool InCoada[n+1];
        vector < pair <int,int> > G[n+1];
        while(m--)
        {
            f>>x>>y>>c;
            G[x].push_back(make_pair(y,c));
        }

        D[1]=0;
        Coada.push(1);
        InCoada[1] = true;
        while(!Coada.empty())
        {
            int nodCurent = Coada.top();
            Coada.pop();
            InCoada[nodCurent] = false;
            for(size_t i = 0; i < G[nodCurent].size(); i++)
            {
                int Vecin = G[nodCurent][i].first;
                int Cost = G[nodCurent][i].second;
                if(D[nodCurent] + Cost < D[Vecin])
                {
                    D[Vecin] = D[nodCurent] + Cost;
                    if(InCoada[Vecin] == false)
                    {
                        Coada.push(Vecin);
                        InCoada[Vecin] = true;
                    }
                }
            }
        }
        for(int i=2;i<=n;++i)
            g<<D[i]<<' ';
    f.close();
    g.close();
    return 0;
}