#include <fstream>
#define MAX 50001
#define MAX2 250001
using namespace std;


long n, m;
struct muchie{
    int v1, v2;
    int cost;
};

long d[MAX];
//int T[100];
muchie a[MAX2];

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


int main()
{
    Read();
    Bellman();
               
    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> n;
    fin >> m;
    for (int i = 1; i<=m; i++)
    {
        fin >> a[i].v1;
        fin >> a[i].v2;
        fin >> a[i].cost;
        if (a[i].v1 == 1) d[a[i].v2] = a[i].cost;
    }
    for (int i = 1; i<= n; i++)
    {
        if (d[i] == 0) d[i] = MAX;
    }
    d[1] = 0;    
}

void Bellman()
{
    int ok = 1;
    while (ok)
    {
        ok = 0;
        for (int i = 1; i<=m; i++)
        {
            if(d[a[i].v2]>d[a[i].v1]+a[i].cost)
			{
  	             d[a[i].v2]=d[a[i].v1]+a[i].cost;
	             ok = 1;
			}
        }
    }
    
    for (int i = 2; i<= n; i++)
    {
        fout << d[i] << " ";
    }
}