#include <fstream>
#include <vector>
#include <queue>
#define INF 2000000069
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");

struct elem
{
    int y,c;
    bool operator < (const elem &a) const
    {
        return c>a.c;
    }
};

vector <elem> a[50002];
priority_queue <elem> pq;
int sol[50002];

void dijkstra()
{
    int i;
    pq.push({1,0});
    while (!pq.empty())
    {
        int y=pq.top().y,c=pq.top().c;
        {
            if (c==sol[y])
            {
                for (i=0;i<a[y].size();i++)
                {
                    int ny=a[y][i].y,cost=a[y][i].c;
                    if (sol[y]+cost<sol[ny])
                    {
                        sol[ny]=sol[y]+cost;
                        pq.push({ny,sol[ny]});
                    }
                }
            }
        }
        pq.pop();
    }
}

int main()
{
    int n,m,i;
    cin>>n>>m;
    int x,y,c;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        a[x].push_back({y,c});
    }
    for(i=2;i<=n;i++)
        sol[i]=INF;
    dijkstra();
    for (i=2;i<=n;i++)
    {
        if (sol[i]==INF) cout<<"0 ";
        else cout<<sol[i]<<' ';
    }
}