#include <cstdio>
#include <vector>
#define DMAX 50010
#define INF 100000000
using namespace std;

FILE * fin = fopen ("dijkstra.in", "r");
FILE * fout = fopen ("dijkstra.out", "w");

//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();
    
    fclose(fin);
    fclose(fout);
    return 0;
}

void citire()
{
    int i, m, a;
    tip aux;
    
    fscanf(fin, "%d %d", &n, &m);
    for (i=1; i<=m; i++)
    {
        fscanf(fin, "%d %d %d", &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)
            fprintf(fout, "0 ");
        else
            fprintf (fout, "%d ", dist[i]);
}