#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define nmax 50002
#define inf 20000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod{
    int v,c;
};

class cmp{
public:
    bool operator()(nod A, nod B)
    {
        return A.c>B.c;
    }
};

vector <nod> graf[nmax];
priority_queue <nod,vector<nod>,cmp> coada;
int dist[nmax],n,m;

bitset  <nmax> viz;

inline void citire ()
{
   fin>>n>>m;
   for (int i=1;i<=m;i++)
   {
       int x,y,c;
       fin>>x>>y>>c;
       graf[x].push_back({y,c});
   }
   for (int i=2;i<=n;i++)
       dist[i]=inf;
}
inline void rezolvare ()
{
    coada.push({1,0});
    int ma=0,ns;
    while (!coada.empty())
    {
        ns=coada.top().v;
        ma=coada.top().c;
        coada.pop();
        if (viz[ns]==0)
        {
            int lg=graf[ns].size()-1;
            for (int i=0;i<=lg;i++)
            {
                int v=graf[ns][i].v;
                int cost=graf[ns][i].c;
                if (ma+cost<dist[v]&&viz[v]==0)
                {
                    dist[v]=ma+cost;
                    coada.push({v,dist[v]});
                }
            }
        }
        viz[ns]=1;
    }
}
inline void scriere ()
{
    for (int i=1;i<=n;i++)
        if (dist[i]==inf)
            dist[i]=0;
    for (int i=2;i<=n;i++)
        fout<<dist[i]<<" ";
}
int main()
{
    citire();
    rezolvare();
    scriere ();
    return 0;
}