#include <fstream>
#include <vector>
#include <set>
#define nmax 50005
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int dmin[nmax],pre[nmax],uz[nmax];
set < pair<int,int > > s;
const int INF = 1e9;
int n,m,start;
struct arc
{
    int vf;
    int c;
};
vector <arc> G[nmax];
int lg[nmax];
void citire()
{
    arc aux;
    fin >> n >> m;
    int x,y,c;
    while (fin >> x >> y >> c)
    {
        //adaug pe y in lista de adiacenta a lui x
        /*G[x][lg[x]].vf = y;
        G[x][lg[x]].c = c;
        lg[x]++;*/
        aux.vf = y;
        aux.c = c;
        G[x].push_back(aux);
    }
}
void dijkstra()
{
    int i,j;
    //initializez
    start = 1;
    uz[start] = 1;
    for (i=1;i<=n;i++)
    {
        pre[i] = start;
        dmin[i] = INF;
    }
    dmin[start] = 0;
    pre[start] = 0;
    s.insert(make_pair(0,start));
    while (!s.empty())
    {
        int vfmin;
        pair<int,int> aux;
        aux = *s.begin();
        vfmin = aux.second;
        s.erase(aux);
        for (i=0;i<G[vfmin].size();i++)
        {
            if (dmin[G[vfmin][i].vf] > dmin[vfmin] + G[vfmin][i].c)
            {
                if (dmin[G[vfmin][i].vf]!=INF)
                {
                    aux.first = dmin[G[vfmin][i].vf];
                    aux.second = G[vfmin][i].vf;
                    s.erase(aux);
                }
                dmin[G[vfmin][i].vf] = dmin[vfmin] + G[vfmin][i].c;
                aux.first = dmin[vfmin] + G[vfmin][i].c;
                aux.second = G[vfmin][i].vf;
                s.insert(aux);
            }
        }
    }
}
void afisare()
{
    int i;
    for (i=2;i<=n;i++)
        if(dmin[i] == INF)
            fout << "0" << ' ';
        else
            fout << dmin[i] << ' ';
    fout << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    citire();
    dijkstra();
    afisare();
    return 0;
}