#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <limits.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,source,dist[50001],x,y,cost,costul,vecin,i;
struct compare
{
    bool operator()(int x,int y)
    {
        return dist[x]>dist[y];
    }
};
priority_queue <int,vector<int>,compare> pQ;
vector < pair <int,int> > a[50001];
bitset <50001> viz;
int main()
{
    in>>n>>m;
    for (i=1; i<=m; ++i)
    {
        in>>x>>y>>cost;
        a[x].push_back(make_pair(y,cost));
    }
    for (i=1; i<=n; ++i)
        dist[i]=INT_MAX;
    source=1;
    dist[source]=0;
    pQ.push(source);
    viz[source]=1;
    while (!pQ.empty())
    {
        x=pQ.top();
        for (i=0; i<a[x].size(); ++i)
        {
            vecin=a[x][i].first;
            costul=a[x][i].second;
            if (dist[x]+costul<dist[vecin])
            {
                dist[vecin]=dist[x]+costul;
                if (!viz[vecin])
                {
                    pQ.push(vecin);
                    viz[vecin]=1;
                }
            }
        }
        pQ.pop();
    }
    for (i=2; i<=n; ++i)
    {
        if (dist[i]==INT_MAX)
            out<<"0 ";
        else
            out<<dist[i]<<" ";
    }
    out<<"\n";

}