#include <iostream>
#include <fstream>

#define maxN 1000

using namespace std;

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

int n,m,a[maxN][maxN],d[maxN],heap[maxN];

void citire()
{
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int x,y;
        fin>>x>>y;
        fin>>a[x][y];
    }
}

void init()
{
    for (int i=1; i<=n; ++i)
        heap[i]=1<<30;
}

void cautMin(int &x)
{
    int distMin=1<<30;
    for (int i=1; i<=n; ++i)
        if (heap[i]<distMin && heap[i]!=-1) { x=i; distMin=heap[i]; }
    heap[x]=-1;
    d[x]=distMin;
}

void Dijkstra(int x)
{
    heap[x]=0;
    int existaNoduri=n;

    while (existaNoduri--)
    {
        cautMin(x);
        for (int i=1; i<=n; ++i)
            if (a[x][i] && d[x] + a[x][i] < heap[i])
                heap[i]=d[x]+a[x][i];
    }
}

void sol()
{
    for (int i=1; i<=n; ++i)
        fout<<d[i]<<' ';
}

int main()
{
    citire();
    init();
    Dijkstra(1);
    sol();
    return 0;
}