#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#define INF (1<<30)
const int NMAX = 50001;
int n,m,dmax[NMAX],v[NMAX],x,y,c;
vector < pair < int , int > > g[NMAX];

struct comp
{
    bool operator()(int x,int y)
    {
        return dmax[x]>dmax[y];
    }
};
priority_queue<int , vector<int> , comp> q;
void dijkstra(int nod)
{

    for(int i=1;i<=n;i++){
        dmax[i]=INF;
        v[i]=0;
    }
        q.push(nod);
        dmax[nod]=0;
        v[nod]=1;
        while(!q.empty())
        {
            int nc=q.top();
            v[nc]=0;
            q.pop();
            for(size_t i=0;i<g[nc].size();i++)
            {
                int vecin=g[nc][i].first;
                int cost=g[nc][i].second;
                if(dmax[vecin]>dmax[nc]+cost)
                {
                    dmax[vecin]=dmax[nc]+cost;
                    if(!v[vecin])
                    {
                        q.push(vecin);
                        v[vecin]=true;
                    }
                }
            }
        }

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