#include <fstream>
#include <vector>
#define DMAX 50010
#define INF 100000000
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct tip {int nod, val;};

void citire();
void rez();
void afisare();
void init();

int n;
vector <tip> graf[DMAX];

int dist[DMAX];
bool use[DMAX];

int valmin, indmin;

int main()
{
    citire();
    rez();
    afisare();
    
    fin.close();
    fout.close();
    return 0;
}

void citire()
{
    int i, m, a;
    tip aux;
    
    fin>> n>> m;
    for (i=1; i<=m; i++)
    {
        fin>>a>> aux.nod>> aux.val;
        graf[a].push_back(aux);
    }
}

void rez()
{
    int i;
    vector <tip> ::iterator it;
    init();
    
    while (valmin!=INF)
    {
        use[indmin]=1;
        
        for (it=graf[indmin].begin(); it!=graf[indmin].end(); it++)
        {
            if (!use[it->nod])
            {
                if (dist[it->nod] > dist[indmin] + it->val)
                    dist[it->nod] = dist[indmin] + it->val;
            }
        }
        
        valmin = INF;
        for (i=1; i<=n; i++)
            if (!use[i] && dist[i]<valmin)
            {
                valmin = dist[i];
                indmin = i;
            }
    }
}

void init()
{
    int i;
    vector <tip> ::iterator it;
    
    for (i=2; i<=n; i++) dist[i]=INF;
    
    valmin = INF;
    for (it=graf[1].begin(); it!=graf[1].end(); it++)
    {
        dist[it->nod] = it->val;
        if (valmin > it->val)
        {
            valmin = it->val;
            indmin = it->nod;
        }
    }
    
    use[1]=1;
}

void afisare()
{
    int i;

    for (i=2; i<=n; i++)
        if (dist[i]==INF)
            fout<< "0 ";
        else
            fout<< dist[i]<< ' ';
}