//#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define oo 99999999

using namespace std;

ifstream f("dijkstra.in");
ofstream cout("dijkstra.out");

int n, m, d[50005], viz[50005]; // d=distanta
vector < pair <int, int> > a[50005];
priority_queue < pair<int, int> > h;


void dijkstra()
{
    int i, nod;
    for (i=1; i<=n; i++) d[i]=oo;

    d[1]=0;

    h.push(make_pair(0, 1));
    while (!h.empty())
    {
        nod=h.top().second;
        h.pop();
        if (viz[nod]==0)
        {
            viz[nod]=1;
            for (i=0; i<a[nod].size(); i++)
            {
                int y, val;

                y=a[nod][i].first;
                val=a[nod][i].second;
                // obvious drum de la nodul y cu costul val
                if (d[y]>d[nod]+val)
                {
                    d[y]=d[nod]+val;
                    h.push(make_pair(-d[y], y));
                }
            }
        }
    }
}
int main()
{
    int i, x, y, val;

    f>>n>>m;
    for (i=1; i<=m; i++)
    {
        f>>x>>y>>val;
        a[x].push_back(make_pair(y, val));
    }

    dijkstra();

    for (i=2; i<=n; i++)
      if (d[i]!=oo) cout<<d[i]<<" ";
      else cout<<0<<" ";

    return 0;
}