#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

vector <int> graph[100005];
vector <int> graphc[100005];
int viz[100005],dist[100005];
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n,m,a,b,c,i;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        graph[a].push_back(b);
        graphc[a].push_back(c);
    }
    int s=1;
    dist[s]=0;
    for(i=2; i<=n; i++)
        dist[i]=100007;
    int index,j,mini=100007;
    for(i=1; i<=n; i++)
    {
        mini=100007;
        for(j=1; j<=n; j++)
        {
            if (dist[j]<mini && viz[j]==0)
            {
                mini=dist[j];
                index=j;
            }
        }
        viz[index]=1;
        int lim=graph[index].size();
        for(j=0; j<lim; j++)
        {
            int vecin=graph[index][j];
            int cost=graphc[index][j];
            if (dist[index]+cost<dist[vecin])
                dist[vecin]=dist[index]+cost;
        }
    }

    for (i=2; i<=n; i++)
        if(dist[i]==100007)
        g<<"0"<<" ";
        else
            g<<dist[i]<<" ";

}