#include <fstream>
#include <cstring>
#include <vector>

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

const long int NMAX = 50005;
const int INFINIT = 1 << 30;

struct edge {
    int x, y, z;
};

int N, M, dist[NMAX];
vector < vector < edge > > lista(NMAX);

void init()
{
    for(int i = 1; i <= N; i++)
        dist[i] = INFINIT;
}

void dijkstra(int nod)
{
    vector < int > coada;
    dist[nod] = 0;
    for(unsigned int i = 0; i < lista[nod].size(); i++)
    {
        dist[lista[nod][i].y] = lista[nod][i].z;
        coada.push_back(lista[nod][i].y);
    }
    
    while(!coada.empty())
    {
        int mini = 0;
        for(unsigned int i = 1; i < coada.size(); i++)
            if(dist[coada[mini]] > dist[coada[i]])
                mini = i;
        int node = coada[mini];
        coada.erase(coada.begin() + mini);
        
        for(unsigned int i = 0; i < lista[node].size(); i++)
        {
            if(dist[lista[node][i].y] == INFINIT)
                coada.push_back(lista[node][i].y);
            if(dist[lista[node][i].y] > dist[lista[node][i].x] + lista[node][i].z)
                dist[lista[node][i].y] = dist[lista[node][i].x] + lista[node][i].z;
        }
    }
    
    for(int i = 2; i <= N; i++)
        if(dist[i] == INFINIT)
            fout << 0 << ' ';
        else
            fout << dist[i] << ' ';
}

void char_scan(int &x, int &y, int &z)
{
    char sir[50];
    fin.getline(sir, 50);
    unsigned long lg = strlen(sir);
    unsigned int k = 0;
    while(sir[k] != ' ')
        x = x * 10 + (sir[k++] - '0');
    k++;
    while(sir[k] != ' ')
        y = y * 10 + (sir[k++] - '0');
    k++;
    while(k < lg)
        z = z * 10 + (sir[k++] - '0');
}

void char_scan(int &N, int &M)
{
    char sir[20];
    fin.getline(sir, 20);
    unsigned long lg = strlen(sir);
    unsigned int k = 0;
    while(sir[k] != ' ')
        N = N * 10 + (sir[k++] - '0');
    k++;
    while(k < lg)
        M = M * 10 + (sir[k++] - '0');
}

void process_input()
{
    char_scan(N, M);
    for(int i = 0 ; i < M; i++)
    {
        int x = 0, y = 0, z = 0;
        char_scan(x, y, z);
        edge e;
        e.x = x; e.y = y; e.z = z;
        lista[x].push_back(e);
    }
}

int main()
{
    process_input();
    init();
    
    dijkstra(1);
    fin.close();
    fout.close();
    return 0;
}