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

using namespace std;

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

const int pinf=1000000;

int n,m,D[100005],nstart;
bool viz[100005];

vector < pair < int,int > > G[100005];
struct compara
{
    bool operator()(int x,int y)
    {
        return D[x]>D[y];
    }
};

priority_queue < int, vector < int >, compara> Coada;


void Citeste()
{int x,y,c;
    fin>>n>>m;
    while (fin>>x>>y>>c)
    {
        G[x].push_back(make_pair(y,c));
    }
}
void Dijkstra(int start)
{int i;
    for (i=1;i<=n;i++)
        D[i]=pinf;
    D[start]=0;
    Coada.push(start);
    viz[start]=1;
    while (!Coada.empty())
    {
        int ncr=Coada.top();
        Coada.pop();
        viz[ncr]=0;
        for (size_t i=0;i<G[ncr].size();i++)
        {
            int Vecin=G[ncr][i].first;
            int cost=G[ncr][i].second;
            if (D[ncr]+cost<D[Vecin])
            {
                D[Vecin]=D[ncr]+cost;
                if (viz[Vecin]==0)
                {
                    Coada.push(Vecin);
                    viz[Vecin]=1;
                }
            }
        }
    }
}
void Afiseaza()
{int i;
    for (i=2;i<=n;i++)
    {
        if (D[i]!=pinf)
            fout<<D[i]<<" ";
        else fout<<0<<" ";
    }
}
int main()
{
    Citeste();
    Dijkstra(1);
    Afiseaza();
    return 0;
}