// BELLMAN-FORD CU COADA

#include <fstream>
#include <vector>
#include <queue>

#define NMAX 50001
#define MMAX 250001
#define INF 99999999
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <pair<int,int> > cm[MMAX];
int n,m,d[NMAX];

void citire()
{
    int a,b,c;
    fin>>n>>m;
    for (int i=0;i<m;++i)
    {
        fin>>a>>b>>c;
        cm[a].push_back(make_pair(b,c));
    }
}
void bellman_ford_coada(int x0)
{
    //Declaratii
    queue<int> q;
    int in[NMAX],k;
    //Initializari
    for(int i=0;i<NMAX;++i)
    {
        d[i]=INF;
        in[i]=0;
    }
    d[x0]=0;
    q.push(x0);
    in[x0]=1;
    //Algoritmul
    while (!q.empty())
    {
        k=q.front();
        q.pop();
        in[k]=0;
        for (int i=0;i<cm[k].size();++i)
            if (d[cm[k][i].first]>d[k]+cm[k][i].second)
            {
                d[cm[k][i].first]=d[k]+cm[k][i].second;
                if (!in[cm[k][i].first])
                {
                    q.push(cm[k][i].first);
                    in[cm[k][i].first]=1;
                }
            }
    }

}

void afisare()
{
    for (int i=2;i<=n;++i)
    {
        fout<<d[i]<<" ";
    }
    fout<<'\n';
}
int main()
{
    citire();
    bellman_ford_coada(1);
    afisare();
    fin.close();
    fout.close();
    return 0;
}