#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> mu;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
bool inq[50004];
int cost[50004],n,m,x,y,c;
const int inf=0x3f3f3f3f;
vector<mu>g[50004];
void dijkstra(int nodS)
{
    priority_queue<int,vector<int>,greater<int>>q;
    int nc;
    q.push(nodS);
    cost[nodS]=0;
    inq[nodS]=true;
    while(!q.empty())
    {
        nc=q.top();
        q.pop();
        inq[nc]=false;
        for(unsigned int i=0;i<g[nc].size();i++)
        {
            if(cost[g[nc][i].first]>cost[nc]+g[nc][i].second)
            {
                cost[g[nc][i].first]=cost[nc]+g[nc][i].second;
                if(!inq[g[nc][i].first])
                {
                    q.push(g[nc][i].first);
                    inq[g[nc][i].first]=true;
                }
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        cost[i]=inf;
    while(m--)
    {
        fin>>x>>y>>c;
        g[x].push_back({y,c});
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
        if(cost[i]!=inf)
            fout<<cost[i]<<' ';
        else
            fout<<0<<' ';
    return 0;
}