#define INF 0x3f3f3f3f
#define MAXN 50004
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
 
struct vecin{
    int y,cost;
 
    bool operator <(const vecin& other) const
    {   if(cost != other.cost)
            return cost<other.cost;
        return y<other.y;
    }
};
 
int n,m;
int dmin[MAXN];
vector<vecin>graf[MAXN];
set<vecin>q;
 
 
void read()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        graf[x].push_back({y,c});
    }
}
 
 
void solve()
{
    for(int i=2;i<=n;i++)
    {
        dmin[i]=INF;
    }
    q.insert({1,0});
    while (!q.empty())
    {
        int top=q.begin()->y;
        q.erase(q.begin());
 
         for(const vecin& v:graf[top])
         {
             int nc=dmin[top]+v.cost;
             if(dmin[v.y]>nc)
             {
                 if(dmin[v.y]!=INF)
                     q.erase({v.y,dmin[v.y]});
                 dmin[v.y]=nc;
                 q.insert({v.y,dmin[v.y]});
             }
         }
    }
}
 
void write()
{
     for(int i=2;i<=n;i++)
        if(dmin[i]==INF)
            fout<<"0"<<" ";
    else
        fout<<dmin[i]<<" ";
}
 
 
int main( ) {
    read();
    solve();
    write();
    return 0;
}